D. Покраска ребер
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан ориентированный граф из $$$n$$$ вершин и $$$m$$$ ориентированных ребер. Гарантируется, что в нем нет ни петель, ни кратных ребер.

Определим $$$k$$$-покраску орграфа следующим образом: мы красим каждое ребро в один из $$$k$$$ цветов. $$$k$$$-покраска является хорошей тогда и только тогда, когда в графе не существует цикла, состоящего из ребер одного цвета.

Найдите хорошую $$$k$$$-покраску с минимально возможным значением $$$k$$$.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 5000$$$, $$$1 \le m \le 5000$$$) — количество вершин и ребер, соответственно.

Следующие $$$m$$$ строк содержат описание ребер — по одному в строке. Каждое ребро задается парой целых чисел $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — они обозначают ребро из вершины $$$u$$$ в вершину $$$v$$$.

Гарантируется, что каждая упорядоченная пара $$$(u, v)$$$ входит в список ребер не более одного раза.

Выходные данные

В первой строке выведите одно целое число $$$k$$$ — количество цветов в $$$k$$$-покраске графа.

Во второй строке выведите $$$m$$$ целых чисел $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le k$$$), где $$$c_i$$$ — цвет $$$i$$$-го ребра (ребра нумеруются в том порядке, в котором заданы во входных данных).

Если ответов несколько, выведите любой (но все равно надо минимизировать $$$k$$$).

Примеры
Входные данные
4 5
1 2
1 3
3 4
2 4
1 4
Выходные данные
1
1 1 1 1 1
Входные данные
3 3
1 2
2 3
3 1
Выходные данные
2
1 1 2