CF1205D.Almost All

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.

给你一棵包含 $n$ 个节点的树。你需要在它的每条边上写上一个非负整数，使得以下条件成立：

对于任意两个节点 $i$、$j$，考察它们之间的唯一路径，并计算该路径上所有边所写数字之和。将所有这样得到的和写在黑板上。那么，黑板上必须至少出现一次从 $1$ 到 $\lfloor \frac{2n^2}{9} \rfloor$ 的每一个整数。

题目保证这样的赋值方案一定存在。

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.

第一行包含一个整数 $n$（$1 \le n \le 1000$）—— 表示节点的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，且 $u \neq v$），表示节点 $u$ 与节点 $v$ 之间存在一条边。保证这些边构成一棵树。

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.

输出 $n-1$ 行，每行格式为 $u$ $v$ $x$（其中 $0 \le x \le 10^6$），表示你在顶点 $u$ 与 $v$ 之间的边上写下了数字 $x$。

所输出的边集 $(u, v)$ 必须与输入图的边集完全一致，但你可以以任意顺序输出这些边；此外，每条边的两个端点 $u$、$v$ 的顺序也可以与输入中不同。

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.

在第一个例子中，节点 $1$ 与节点 $2$ 之间的距离为 $2$，节点 $2$ 与节点 $3$ 之间的距离为 $1$，节点 $1$ 与节点 $3$ 之间的距离为 $3$。

在第三个例子中，黑板上将写下从 $1$ 到 $9$（含）的所有数字，而我们只需从 $1$ 到 $5$ 即可通过测试。