3 Super Coloring

Ordinary graph coloring is a well-known problem. Hyeongjin got bored of it and invented a new coloring rule called super coloring.

A super coloring of a graph assigns a color to each vertex and must satisfy the following conditions for every two distinct vertices $u, v$.

• If $u$ and $v$ are connected by an edge, their colors must be different.
• If $u$ and $v$ are not connected by an edge, their colors must be the same.

Hyeongjin also decided to define a new graph operation. Given a graph, its complement graph is obtained by removing every edge that originally existed and adding every edge that originally did not exist. Self-loops are not considered.

Hyeongjin wants to know whether the complement graph of the given graph can be super-colored using only $3$ colors.

Determine whether it is possible, and if it is possible, output one valid coloring.

The input is given in the following format.

$n\ m$ $u_1\ v_1$ $u_2\ v_2$ $\cdots$ $u_m\ v_m$

The given graph is a simple undirected graph with $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$.

If the complement graph can be super-colored, print yes on the first line. Otherwise, print no.

If it is possible, print $n$ integers $c_1, c_2, \ldots, c_n$ on the second line. $c_i$ is the color of vertex $i$, and must be one of $1$, $2$, and $3$.

If there are multiple valid colorings, you may print any of them.

• $1 \le n \le 200\,000$.
• $0 \le m \le 200\,000$.
• $1 \le u_i, v_i \le n$.
• $u_i \ne v_i$.
• No edge appears more than once.