#91 3 Super Coloring

Statement

Statement language

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.

Input

The input is given in the following format.

$n\ m$ $u_1\ v_1$ $u_{2}$

Output

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. is the color of vertex , and must be one of , , and .

Constraints

$1 \le n \le 200\,000$ .
$0 \le m \le 200\,000$ .
$1 \leq u_{i},$ .

Subtasks

#	Score	Constraints
1	0	Sample-style data.
2	100	Full constraints.

Samples

Sample 1

Input

2
2
4

Output

yes
1 1 2 2

In the complement graph, adjacent vertices have different colors, and non-adjacent vertices have the same color.

Sample 2

Input

2
2
3

Output

There is no coloring satisfying the conditions.

Sample 3

Input

4 0

Output

The original graph has no edges, so its complement is the complete graph on $4$ vertices. It requires $4$ distinct colors, so $3$ colors are not enough.