Ли планировал приблизиться к сердцу Маштали, чтобы осуществить свой коварный план (о котором мы пока не знаем), поэтому он решил украсить граф Маштали. Но он установил для себя несколько правил. А еще он был слишком занят своими планами, что у него не было времени на такие мелкие дела, поэтому он обратился за помощью к вам.
Граф Маштали — это неориентированный взвешенный граф с \(n\) вершинами и \(m\) ребрами с весами, равными либо \(1\), либо \(2\). Ли хочет направить ребра графа Маштали так, чтобы он был как можно красивее.
Ли считает, что красота направленного взвешенного графа равна количеству его вершин Одиссея. Вершина \(v\) является вершиной Оддисея, если \(|d^+(v) - d^-(v)| = 1\), где \(d^+(v)\) — сумма весов исходящих из \(v\) ребер, а \(d^-(v)\) — сумма весов входящих в \(v\) ребер.
Найдите наибольшую возможную красоту графа, которую Ли может получить, направляя ребра графа Маштали. Кроме того, найдите любой способ ее достижения.
Обратите внимание, что вы должны ориентировать каждое из ребер.
Выходные данные
В первой строке выведите одно целое число — максимальную красоту графа, которую может достичь Ли.
Во второй строке выведите строку длины \(m\), состоящую из \(1\) и \(2\) — направления ребер.
Если вы решили направить \(i\)-е ребро из вершины \(u_i\) в вершину \(v_i\), то \(i\)-й символ строки должен быть \(1\). В противном случае он должен быть равен \(2\).