Description

There are $N$ vertices and $N-1$ undirected edges. Define the cost of a directed graph as the length of the longest path in this directed graph.

Now assign directions to these $N-1$ undirected edges so that the cost of the resulting directed graph is minimized.

Output one such direction assignment.

Input Format

The first line contains an integer $N$, the number of vertices.
The next $N-1$ lines each contain two integers $a_i, b_i$, representing an edge.

Output Format

Output $N-1$ lines, each containing one integer $r$:

• If $r=1$, it means the direction is from $a_i$ to $b_i$.
• If $r=0$, it means the direction is from $b_i$ to $a_i$.

3
1 2
2 3

1
0

4
2 1
1 3
4 1

0
1
0

Hint

Explanation of Sample 1

As shown in the figure:

The cost of this graph is $1$. Note that $0\ 1$ is also an optimal solution.

Explanation of Sample 2

As shown in the figure:

Constraints

For $30\%$ of the testdata, $N \le 20$.
For $100\%$ of the testdata, $2 \le N \le 10^5$, $1 \le a_i, b_i \le N$.

This problem uses Special Judge.
You only need to output any valid solution.

Notes

Translated from COCI 2015-2016 #3 C MOLEKULE.

Translated by ChatGPT 5