Orienting Molecular Bonds

Scientists in a chemical lab in Croatia study the chemical bonds between molecules. Their current subject is a group of molecules of the compound nitro hydrogen laminate.

The compound consists of $N$ molecules held together by $N-1$ covalent bonds, and every molecule is tied to the rest directly or indirectly, so the bonds form one connected structure.

The scientists want to turn every covalent bond into a directed bond. The new compound is unstable, so each molecule emits a large number of impulses that travel to other molecules along the directed bonds. An impulse can cross a bond only in the direction of that bond.

The instability of the compound is the largest number of bonds a single impulse can cross on its travel. The scientists want to orient the bonds so that the compound is as stable as possible, that is, so that the instability is minimal.

Determine the direction of every covalent bond.

The first line contains the number of molecules $N$ ($2 \le N \le 100\,000$).

Each of the next $N-1$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$), meaning that molecules $a_i$ and $b_i$ are joined by a covalent bond. The bonds always form a tree.

Print $N-1$ lines. Line $i$ gives the direction of the $i$-th bond of the input: print 1 if the bond is directed from $a_i$ to $b_i$, and 0 if it is directed from $b_i$ to $a_i$.

Several orientations reach the minimal instability, so only the one fixed by the following rule is accepted. Measure the distance from molecule 1 to each molecule as the number of bonds on the way, then direct every bond from its endpoint at even distance to its endpoint at odd distance. The two endpoints of a bond differ in distance by exactly 1, so the direction is determined.