Problem H
Hyacinth
Your bosses at NWERC want you to figure out a procedure for assigning frequencies to the NICs such that the number of frequencies in use is maximized, subject to the constraint that all pairs of adjacent nodes must be able to communicate. A frequency is considered used if any pair of nodes within range of each other share that frequency. In the mesh network that you will be dealing with, each node is equipped with exactly two NICs (i.e., each node can use at most two frequencies). Since you are new at NWERC, your bosses further restrict the network layouts to make your job easier: the network graph will form a tree.
Input
The input consists of:
-
one line with one integer $n$ ($2 \leq n \leq 10\, 000$), the number of nodes in the network;
-
$n-1$ lines, each with two space-separated integers $i$ and $j$, with $1 \leq i,j \leq n$ signifying that the (one-indexed) network nodes $i$ and $j$ are in range of each other.
Output
Output a frequency assignment for each of the $2n$ NICs such that all adjacent nodes can communicate and the number of used frequencies is maximized. You should output $n$ lines, where the $i$th line contains the two frequencies of network node $i$. Valid frequencies are nonnegative integers less than $10^9$.
Sample Input 1 | Sample Output 1 |
---|---|
2 1 2 |
23 42 42 23 |
Sample Input 2 | Sample Output 2 |
---|---|
14 1 2 1 3 1 4 2 5 2 6 3 7 4 8 4 9 4 10 7 11 7 12 7 13 7 14 |
4711 815 666 4711 4711 42 815 7 47 666 666 54 23 42 7 2 7 1 7 3 23 4 42 5 23 6 42 8 |