Description

Input

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

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.

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