Berland has \(n\) cities, some of which are connected by roads. Each road is bidirectional, connects two distinct cities and for each two cities there's at most one road connecting them.
The president of Berland decided to split country into \(r\) states in such a way that each city will belong to exactly one of these \(r\) states.
After this split each road will connect either cities of the same state or cities of the different states. Let's call roads that connect two cities of the same state "inner" roads.
The president doesn't like odd people, odd cities and odd numbers, so he wants this split to be done in such a way that each city would have even number of "inner" roads connected to it.
Please help president to find smallest possible \(r\) for which such a split exists.
Output
For each test case first print a line containing a single integer \(r\) — smallest possible number of states for which required split is possible. In the next line print \(n\) space-separated integers in range from \(1\) to \(r\), inclusive, where the \(j\)-th number denotes number of state for the \(j\)-th city. If there are multiple solutions, print any.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 3
1 2
2 5
1 5
6 5
1 2
2 3
3 4
4 2
4 1
|
1
1 1 1 1 1
2
2 1 1 1 1 1
|