Odd Federalization
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: constructive algorithms

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.

Input format:
The input contains one or several test cases. The first input line contains a single integer number $$$t$$$ — number of test cases. Then, $$$t$$$ test cases follow. Solve test cases separately, test cases are completely independent and do not affect each other.

Then $$$t$$$ blocks of input data follow. Each block starts from empty line which separates it from the remaining input data. The second line of each block contains two space-separated integers $$$n$$$, $$$m$$$ ($$$1 \le n \le 2000$$$, $$$0 \le m \le 10000$$$) — the number of cities and number of roads in the Berland. Each of the next $$$m$$$ lines contains two space-separated integers — $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), which denotes that the $$$i$$$-th road connects cities $$$x_i$$$ and $$$y_i$$$. Each pair of cities are connected by at most one road.

Sum of values $$$n$$$ across all test cases doesn't exceed $$$2000$$$. Sum of values $$$m$$$ across all test cases doesn't exceed $$$10000$$$.

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
2
5 3
1 2
2 5
1 5
6 5
1 2
2 3
3 4
4 2
4 1

Example output:
1
1 1 1 1 1
2
2 1 1 1 1 1

Editorial:
$$$r \le 2$$$ is always enough. Let's prove it (and give a constructive algorithm to build a certificate at the same time).
If all the degrees are even, $$$r=1$$$.
If there is at least one odd vertex, consider $$$v$$$ is an odd vertex (any if there are many of them). Let's $$$u_1, u_2, \dots, u_{2k+1}$$$ are its neighbors. Remove $$$v$$$ from the graph, but for each pair of vertices $$$(u_i, u_j)$$$ ($$$1 \le i < j \le 2k+1$$$) let's toggle an edge between $$$u_i$$$ and $$$u_j$$$. It means that remove an edge $$$(u_i, u_j)$$$ if it exists, and add an edge $$$(u_i, u_j)$$$ if not exists.
Now you have the graph with less number of vertices (the vertex $$$v$$$ has been removed). Let's use recursion to solve problem for the reduced graph.
Now our goal is to add the vertex $$$v$$$ back and revert all the edges $$$(u_i, u_j)$$$. Our goal is to choose such color for $$$v$$$ that it leads to the valid answer for the initial graph. Iterate over vertices $$$u_1, u_2, \dots, u_{2k+1}$$$ and for each of two colors calculate the number of vertices from $$$u_1, u_2, \dots, u_{2k+1}$$$ of its color. As the total number of vertices to analyze is odd, the number for one color will be odd and the number for other color will be even. Paint the vertex $$$v$$$ with the color which has even number of vertices among $$$u_1, u_2, \dots, u_{2k+1}$$$. Also toggle back all edges $$$(u_i, u_j)$$$. Now the graph rolled back to be the initial and you can prove the painting into the two colors is also valid.