410391: GYM104015 I Tree Painting

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Tree Paintingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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.

ExamplesInput
6
1 2
2 3
4 2
4 6
5 4
Output
YES
0 0 0 1 1 1 
Input
4
3 1
3 2
3 4
Output
NO
Note

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.

加入题单

上一题 下一题 算法标签: