Maxim Vitalievich decided to understand the graphs theory. He studied some theory regarding connected undirected graphs, but here Maksim Vitalievich had difficulties.
Among all types of connected undirected graphs, Maxim Vitalievich understood in detail only trees. Recall that a tree – is a connected graph that does not contain cycles and consists of $$$n$$$ vertices and $$$n - 1$$$ edges. Other kinds of graphs present some difficulties, as they may have cycles or they may not be connected.
To deal with more complex types of graphs, Maxim Vitalyevich decided to represent them as a union of a set of trees. For simplicity, he decided to limit himself to only two trees. In order to represent a graph of $$$n$$$ vertices as a union of two trees, Maxim Vitalievich colored each edge in one of three colors. Next, he built the first $$$n$$$ vertex tree using the $$$1$$$ and $$$3$$$ edges, and the second $$$n$$$ vertex tree – using the $$$2$$$ and $$$3$$$ edges. Thus, if we combine two trees, we get the original graph, since each edge belongs to at least one tree.
The difficulties didn't end there. Maxim Vitalievich noticed that it is quite difficult to color some graphs so that the result is two trees with an initial set of vertices. Therefore, Maxim Vitalievich turned to you for help.
Help Maksim Vitalievich color $$$m$$$ edges of a graph of $$$n$$$ vertices with three colors so that it can be represented as two trees, each of which consists of $$$n$$$ vertices.
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertices and edges in the original graph.
The next $$$m$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ — the numbers of the vertices connected by the $$$i$$$-th edge.
It is guaranteed that the original graph is connected and does not contain multiple edges and loops.
$$$$$$ 2 \le n \le 100 $$$$$$ $$$$$$ n - 1 \le m \le 200 $$$$$$ $$$$$$ 1 \le x_i, y_i \le n$$$$$$
On the first line print "No" (without quotes) if there is no answer.
Otherwise, on the first line print "Yes" (without quotes).
In the second line print $$$m$$$ space-separated integers $$$c_1$$$, $$$c_2$$$, ... $$$c_m$$$, where $$$c_i$$$ ($$$1 \le c_i \le 3$$$) — color of the $$$i$$$-th ribs.
If there are multiple answers, print any of them.
4 4 1 2 1 3 1 4 2 3
Yes 3 1 3 2
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
No
