Almost All
Contest: Codeforces Round 580 (Div. 1)
Difficulty rating: 2700
Tags: constructive algorithms, trees

You are given a tree with $$$n$$$ nodes. You have to write non-negative integers on its edges so that the following condition would be satisfied:

For every two nodes $$$i$$$, $$$j$$$, look at the path between them and count the sum of numbers on the edges of this path. Write all obtained sums on the blackboard. Then every integer from $$$1$$$ to $$$\lfloor \frac{2n^2}{9} \rfloor$$$ has to be written on the blackboard at least once.

It is guaranteed that such an arrangement exists.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of nodes.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), meaning that there is an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree.

Output format:
Output $$$n-1$$$ lines, each of form $$$u$$$ $$$v$$$ $$$x$$$ ($$$0 \le x \le 10^6$$$), which will mean that you wrote number $$$x$$$ on the edge between $$$u$$$, $$$v$$$.

Set of edges $$$(u, v)$$$ has to coincide with the set of edges of the input graph, but you can output edges in any order. You can also output ends of edges in an order different from the order in input.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, distance between nodes $$$1$$$ and $$$2$$$ is equal to $$$2$$$, between nodes $$$2$$$ and $$$3$$$ to $$$1$$$, between $$$1$$$ and $$$3$$$ to $$$3$$$.

In the third example, numbers from $$$1$$$ to $$$9$$$ (inclusive) will be written on the blackboard, while we need just from $$$1$$$ to $$$5$$$ to pass the test.

Example input:
3
2 3
2 1

Example output:
3 2 1
1 2 2

Example input:
4
2 4
2 3
2 1

Example output:
4 2 1
3 2 2
1 2 3

Editorial:
First we prove the following lemma:
Suppose that there are $$$ n $$$ vertices in the tree $$$ G $$$ with the root $$$ v $$$. Let also $$$ 0 <a_1 <a_2 \dots <a_ {n-1} $$$ be any $$$ n-1 $$$ different positive numbers. Then we can arrange non-negative integers on the edges of $$$ G $$$ so that the distances from $$$ v $$$ to the remaining vertices of the tree are $$$ a_1, a_2, \dots, a_{n-1} $$$ in some order.
Proof: for example, by induction. Let $$$ s $$$ be some child of $$$ v $$$ in whose subtree, including $$$ s $$$, there are $$$ m $$$ vertices. Then we write on the edge between $$$ (v, s) $$$ $$$ a_1 $$$, and solve the problem for the subtree $$$ s $$$ and the numbers $$$ a_2-a_1, a_3-a_1, \dots, a_m - a_1 $$$. After that, we discard the subtree of $$$ s $$$ from consideration and fill in the remaining edges for the numbers $$$ a_{m + 1}, \dots, a_{n-1} $$$.
Thus, the lemma is proved.
Now let $$$ c $$$ be the centroid of tree. Root the tree from $$$ c $$$ and let $$$ s_1, s_2, \dots, s_k $$$ be the sizes of the subtrees of his childs (as we know, $$$ s_i \le \frac{n}{2}$$$). Divide the subtrees of the childs into two groups so that size of each group is at least $$$ \lceil \frac{n-1}{3} \rceil $$$. It is possible: while there are at least $$$ 4 $$$ subtrees, there are two for which there are no more than $$$ \frac{n}{2} $$$ vertices in total, then we unite them. When we have $$$ 3 $$$ subtrees left, we will unite two smaller ones into one group. It is easy to see that in each of the two groups there will be at least $$$ \lceil \frac{n-1}{3} \rceil $$$ vertices.
Let the first group have $$$ a $$$ vertices and the second $$$ b $$$. Then, using the lemma, we put the numbers on the edges in $$$ a $$$ and between $$$ c $$$ and $$$ a $$$ so that the distances from $$$ c $$$ to the vertices of the first group are $$$ 1, 2, \dots, a $$$. Similarly, we make the distance from $$$ c $$$ to the vertices of the second group equal to $$$ (a + 1), 2 (a + 1), \dots, b (a + 1) $$$. Then each number from $$$ 1 $$$ to $$$ (a + 1) (b + 1) -1 $$$ can be obtained as the distance between some vertex from the first group and some from the second. It is easy to show that $$$ (a + 1) (b + 1) -1 $$$ for $$$ a + b = n-1 $$$ and $$$ a, b \ge \lceil \frac{n-1}{3} \rceil $$$ cannot be less than $$$ \frac {2n ^ 2} {9} $$$. (For example, we can say that this value is minimized at $$$ a = \frac{n-1}{3} $$$ and get $$$ (a + 1) (b + 1) -1 \ge (\frac{n + 2 }{3}) (\frac{2n + 1}{3}) - 1 = \frac{2n ^ 2 + 5n + 3}{9} - 1 \ge \frac{2n ^ 2}{9} $$$ for $$$ n> 1 $$$ (the case of $$$ n = 1 $$$ is obvious)).
Asymptotics $$$ O (n) $$$ (but a checker takes $$$ O (n ^ 2) $$$)