Hyacinth frequency assignment

In the multi channel mesh network architecture called Hyacinth, every node of a wireless mesh network carries exactly two network interface cards (NICs). You choose one frequency for each NIC. Two nodes that are in range of each other can communicate only if their NICs share at least one frequency, so a single node works with at most two frequencies.

A frequency is used when two nodes that are in range of each other both carry that frequency. The more frequencies the network uses, the better its theoretical throughput. Assign frequencies to the $2n$ NICs so that every pair of nodes in range of each other can communicate, and make the number of used frequencies as large as possible. The links of the network form a tree.

The first line contains one integer $n$ ($2 \le n \le 10\,000$), the number of nodes in the network.

Each of the next $n - 1$ lines contains two integers $i$ and $j$ ($1 \le i, j \le n$), meaning that node $i$ and node $j$ are in range of each other. Nodes are numbered from 1 to $n$, and the given links form a tree.

Print $n$ lines. Line $i$ contains the two frequencies assigned to the two NICs of node $i$. A frequency is a nonnegative integer smaller than $10^9$.

Many assignments reach the maximum, so print the one produced by this rule.

• Sort every adjacency list by node number and root the tree at node 1.
• Frequencies are taken in the order 1, 2, 3, and so on. The value 0 marks a NIC that no link uses.
• If node 1 has exactly one neighbour, give that link frequency 1. If node 1 has two or more neighbours, give the link to its smallest numbered neighbour frequency 1, and give every other link of node 1 frequency 2.
• Run a depth first search from node 1 that always continues into the smallest numbered unvisited neighbour. When the search first reaches a node $v$ other than node 1 and $v$ has at least one child, take the smallest frequency not taken yet and put it on every link from $v$ to its children.
• On line $i$, print the two frequencies of node $i$ in increasing order. If node $i$ takes part in only one frequency, the first value on the line is 0.