Вам дан ориентированный граф из \(n\) вершин и \(m\) ориентированных ребер. Гарантируется, что в нем нет ни петель, ни кратных ребер.
Определим \(k\)-покраску орграфа следующим образом: мы красим каждое ребро в один из \(k\) цветов. \(k\)-покраска является хорошей тогда и только тогда, когда в графе не существует цикла, состоящего из ребер одного цвета.
Найдите хорошую \(k\)-покраску с минимально возможным значением \(k\).
Выходные данные
В первой строке выведите одно целое число \(k\) — количество цветов в \(k\)-покраске графа.
Во второй строке выведите \(m\) целых чисел \(c_1, c_2, \dots, c_m\) (\(1 \le c_i \le k\)), где \(c_i\) — цвет \(i\)-го ребра (ребра нумеруются в том порядке, в котором заданы во входных данных).
Если ответов несколько, выведите любой (но все равно надо минимизировать \(k\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 2
1 3
3 4
2 4
1 4
|
1
1 1 1 1 1
|
|
2
|
3 3
1 2
2 3
3 1
|
2
1 1 2
|