Background

On a small tree stands a fantasy castle. This is the territory of Country E, and Little E is the king of Country E.

To build a perfect Country E, he needs to tell right from wrong and move toward justice.

However, he seems a bit too idealistic. Sometimes there is no perfect rule. Is it black or white? Who can tell?

Problem Description

Given a tree with $n$ nodes rooted at $1$, define the depth $d_i$ of a node as the number of nodes on the simple path from it to the root.

You need to color each node black or white such that the sum of depths of black nodes equals the sum of depths of white nodes. Let $c_i = \{0, 1\}$ represent that node $i$ is black or white, respectively. Then this is $\displaystyle\sum_{c_i=0} d_i = \sum_{c_i=1} d_i$.

If there is no solution, output a single line with one integer $-1$.

Input Format

The first line contains one positive integer $n$.

The next $n - 1$ lines each contain two integers $u_i, v_i$, indicating that there is an edge between node $u_i$ and node $v_i$ in the tree. It is guaranteed that the given edges are not repeated.

Output Format

If there is a solution, output one line with $n$ numbers $c_1 \dots c_n$.

If there is no solution, output a single line with one integer $-1$.

This problem uses a Special Judge. As long as your solution satisfies the condition or correctly determines that there is no solution, you can get the score for this test point.

6
1 2
1 3
2 4
2 5
2 6

0 1 1 1 0 0

5
1 2
1 3
2 4
2 5

-1

Hint

Sample Explanation

For the first set of testdata, the depths of each node are $d = [1, 2, 2, 3, 3, 3]$. The sum of depths of black nodes is $d_1 + d_5 + d_6 = 1 + 3 + 3 = 7$, and the sum of depths of white nodes is $d_2 + d_3 + d_4 = 2 + 2 + 3 = 7$. They are equal, so the sample output is correct. Possible correct outputs include but are not limited to the sample output, 0 1 1 0 0 1, 1 0 0 1 0 1, and so on.

Constraints and Notes

This problem uses bundled tests.

A slash means there is no special restriction in that column.

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le u_i, v_i \le n$, and the input forms a tree.

Translated by ChatGPT 5