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$$$.
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$$$.
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.
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
YES 3 1 2 2 3 3 YES 1 1 1 1 1
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)$$$.
