F. Маштали: космическая одиссея
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ли планировал приблизиться к сердцу Маштали, чтобы осуществить свой коварный план (о котором мы пока не знаем), поэтому он решил украсить граф Маштали. Но он установил для себя несколько правил. А еще он был слишком занят своими планами, что у него не было времени на такие мелкие дела, поэтому он обратился за помощью к вам.

Граф Маштали — это неориентированный взвешенный граф с $$$n$$$ вершинами и $$$m$$$ ребрами с весами, равными либо $$$1$$$, либо $$$2$$$. Ли хочет направить ребра графа Маштали так, чтобы он был как можно красивее.

Ли считает, что красота направленного взвешенного графа равна количеству его вершин Одиссея. Вершина $$$v$$$ является вершиной Оддисея, если $$$|d^+(v) - d^-(v)| = 1$$$, где $$$d^+(v)$$$ — сумма весов исходящих из $$$v$$$ ребер, а $$$d^-(v)$$$ — сумма весов входящих в $$$v$$$ ребер.

Найдите наибольшую возможную красоту графа, которую Ли может получить, направляя ребра графа Маштали. Кроме того, найдите любой способ ее достижения.

Обратите внимание, что вы должны ориентировать каждое из ребер.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ $$$(1 \le n \le 10^5;\; 1 \le m \le 10^5)$$$ — количество вершин и ребер в графе.

В $$$i$$$-й строке следующих $$$m$$$ строк содержится три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ $$$( 1 \le u_i , v_i \le n;\; u_i \neq v_i;\; \bf{w_i \in \{1, 2\}} )$$$ — концы $$$i$$$-го ребра и его вес.

Обратите внимание, что граф не обязательно должен быть связным, и он может содержать мультиребра.

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

В первой строке выведите одно целое число — максимальную красоту графа, которую может достичь Ли.

Во второй строке выведите строку длины $$$m$$$, состоящую из $$$1$$$ и $$$2$$$ — направления ребер.

Если вы решили направить $$$i$$$-е ребро из вершины $$$u_i$$$ в вершину $$$v_i$$$, то $$$i$$$-й символ строки должен быть $$$1$$$. В противном случае он должен быть равен $$$2$$$.

Примеры
Входные данные
6 7
1 2 1
1 3 2
2 3 2
1 4 1
4 5 1
2 5 2
2 6 2
Выходные данные
2
1212212
Входные данные
6 7
1 2 2
1 3 2
2 3 2
1 4 2
4 5 2
2 5 2
2 6 2
Выходные данные
0
1212212
Входные данные
6 7
1 2 1
1 3 1
2 3 1
1 4 1
4 5 1
2 5 1
2 6 1
Выходные данные
2
1212212
Примечание

Объяснение к первому примеру:

вершины $$$2$$$ и $$$5$$$ — вершины Одиссея.

Объяснение для третьего примера:

вершины $$$1$$$ и $$$6$$$ — вершины Одиссея.