C. Color Cycles
time limit per test
10 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a graph$$$^\dag$$$, you must color each vertex in such a way that the following two conditions are met:

  • There is no monochromatic cycle$$$^\ddag$$$ 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.

Determine if it is possible to do so and, if so, provide a valid coloring.

$$$^\dag$$$ A graph is a pair $$$(V, E)$$$, where $$$V$$$ is a set of vertices (numbered from $$$1$$$ to $$$n$$$ in this problem) and $$$E$$$ is a set of unordered pairs $$${u, v}$$$ of distinct vertices, which are called edges.

$$$^\ddag$$$ A cycle in a graph is a list of distinct vertices $$$(v_1, \ldots, v_c)$$$ 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$$$, the number of cases to process.

Each case begins with a line containing two integers $$$n$$$ and $$$m$$$, 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$$$ — the vertices that the $$$i$$$-th edge connects.

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 "SI" followed by an integer $$$C$$$, the number of colors you will use in the coloring. 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.

Scoring
  1. (4 points) $$$m = n-1$$$ and for all $$$1 \leq i \lt n$$$, $$$u_i \leq i$$$, $$$v_i = i+1$$$.
  2. (7 points) $$$m = \frac{n(n-1)}{2}$$$.
  3. (27 points) $$$n + m \leq 100$$$.
  4. (26 points) The sum of $$$(n + m)$$$ for all cases is at most $$$2 \cdot 10^5$$$.
  5. (36 points) No additional restrictions.
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
SI 3
1 2 2 3 3
SI 1
1 1 1 1
Note

$$$1 \leq T \leq 2000$$$.

$$$2 \leq n \leq 10^6$$$.

$$$1 \leq m \leq 3 \cdot 10^6$$$.

$$$1 \leq u_i, v_i \leq n$$$. $$$u_i \neq v_i$$$, and there are no repeated edges.

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