Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a simple undirected graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges. He wants to divide it into $K$ parts (subgraphs) for some integer $K$.

First, Chef divides the vertices in the graph into $K$ sets such that each vertex belongs to exactly one set; the subgraphs and sets are numbered $1$ through $K$ such that for each valid $i$, vertices from the $i$-th set belong to the $i$-th subgraph. Then, Chef checks all the edges in the graph. For an edge connecting vertices $u$ and $v$, if $u$ and $v$ are both in the $i$-th set, then this edge belongs to the $i$-th subgraph. Otherwise, this edge does not belong to any of these $K$ subgraphs.

At the end, Chef checks these $K$ subgraphs. If each subgraph contains an even number of edges, then Chef thinks that this way of dividing the graph is delicious.

Chef wants to divide the graph in a delicious way such that $K$ is the smallest possible. Find the minimum $K$ and one such way to divide the graph.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
Each of the next $M$ lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.

------ Output ------
For each test case, print two lines. The first of these lines should contain a single integer ― the minimum $K$. The second line should contain $N$ space-separated integers, where for each valid $i$, the $i$-th integer denotes the subgraph that vertex $i$ belongs to.

If there are multiple solutions, you may output any one.

------ Constraints ------
$1 ≤ T ≤ 3,000$
$1 ≤ M ≤ 100,000$
$2 ≤ N ≤ 100,000$
$1 ≤ u \neq v ≤ N$
the graph contains no duplicate edges or self-loops
the sum of $N$ over all test cases does not exceed $10^{6}$
the sum of $M$ over all test cases does not exceed $10^{6}$

------ Subtasks ------
Subtask #1 (30 pts): $2 ≤ N ≤ 10$

Subtask #2 (70 pts): original constraints

----- Sample Input 1 ------
1
5 5
1 2
1 3
2 3
2 4
3 4
----- Sample Output 1 ------
2
1 2 1 1 2
----- explanation 1 ------
Example case 1: Subgraph $1$ contains vertices $1$, $3$, $4$ and edges $(1,3)$ and $(3,4)$. Subgraph $2$ contains vertices $2$ and $5$, but no edges.

见题面

见题面