H. Bichromatic Cycles
time limit per test
10 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an undirected graph. You must color each vertex of the graph in such a way that the following two conditions are met:

  • There is no monochromatic cycle$$$^*$$$ in the graph, i.e., there is no cycle whose vertices are all of the same color.
  • For each pair of distinct colors $$$c_1$$$, $$$c_2$$$ that appear in the graph, there exists a bichromatic cycle with colors $$$c_1$$$ and $$$c_2$$$, i.e., there is a cycle that contains at least one vertex of color $$$c_1$$$, at least one vertex of color $$$c_2$$$, and no vertices of any other color.

Report whether or not it is possible to do so, and, if it is, provide a valid coloring.

$$$^*$$$ A cycle in a graph is a list of distinct vertices $$$(v_1, \ldots, v_c)$$$, where $$$c \geq 3$$$, such that for all $$$1 \leq i \lt c$$$ there is an edge between vertices $$$v_i$$$ and $$$v_{i+1}$$$, and there is also an edge between $$$v_c$$$ and $$$v_1$$$.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2000$$$), the number of independent test cases to process.

Each case begins with a line containing two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^6$$$, $$$1 \leq m \leq 3 \cdot 10^6$$$), the number of vertices and the number of edges in the graph, respectively.

This is followed by $$$m$$$ lines, the $$$i$$$-th of which contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — the vertices that the $$$i$$$-th edge connects. There is at most one edge between every pair of vertices.

The sum of $$$(n+m)$$$ for all cases is at most $$$4 \cdot 10^6$$$.

Output

For each case, if there is no valid coloring, print a single line with the word "NO". Otherwise, print a line with the word "YES" followed by an integer $$$C$$$ ($$$1 \leq C \leq n$$$), the number of colors you will use.

Then, print a new line with $$$n$$$ integers between $$$1$$$ and $$$C$$$, the $$$i$$$-th of which is the color assigned to vertex $$$i$$$. For all $$$1 \leq i \leq C$$$, there should be no cycle with vertices of color $$$i$$$, and for all $$$1 \leq i \lt j \leq C$$$, there should be a cycle with vertices of colors $$$i$$$ and $$$j$$$. If there are multiple possible colorings, you can print any of them.

We strongly recommend using fast I/O for this problem.

Example
Input
2
5 8
1 2
1 3
1 4
2 3
5 1
4 3
4 5
5 2
4 2
1 2
3 4
Output
YES 3
1 2 2 3 3
YES 1
1 1 1 1
Note

The figure below shows one possible coloring for the first example. There are no cycles with vertices of the same color, and, for each pair of colors, there exists a cycle with just those two colors: for colors $$$1$$$ and $$$2$$$, the cycle is $$$(1, 2, 3)$$$; for colors $$$1$$$ and $$$3$$$, it is $$$(1, 4, 5)$$$; and for colors $$$2$$$ and $$$3$$$, it is $$$(2, 3, 4, 5)$$$.