410391: GYM104015 I Tree Painting

Monocarp has got a tree consisting of $$$n$$$ vertices, $$$n$$$ is even. A tree is a connected acyclic graph.

Monocarp wants to paint exactly half of the vertices of the tree black, and the other half of the vertices — white. Furthermore, he wants there to be exactly one edge connecting vertices of different colors after all vertices are painted.

Help Monocarp find any coloring that meets these constraints, or report that it is impossible.

The first line contains one even integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of vertices.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) denoting the endpoints of some edge. It is guaranteed that these edges form a tree.

If there is no coloring that meets the constraints, print "NO" (without quotes).

Otherwise, print "YES" in the first line (without quotes). Then, print $$$n$$$ integers $$$0$$$ and/or $$$1$$$ in the second line, where the $$$i$$$-th integer should be $$$0$$$ if the $$$i$$$-th vertex should be painted black, or the $$$i$$$-th integer should be $$$1$$$ if the $$$i$$$-th vertex should be painted white. If there are multiple answers, print any of them.

6
1 2
2 3
4 2
4 6
5 4

YES
0 0 0 1 1 1 

4
3 1
3 2
3 4

NO

In the first example, you should paint the vertices $$$1$$$, $$$2$$$ and $$$3$$$ white, and vertices $$$4$$$, $$$5$$$ and $$$6$$$ — black. Then the only edge connecting two vertices of different colors is the edge between $$$2$$$ and $$$4$$$.

There is no coloring that meets the constraints in the second example.