给你一棵有 $$$n$$$ 个节点的树。您必须在其边缘写入非负整数,以便满足以下条件:
对于每两个节点 $$$i$$$, $$$j$$$,查看它们之间的路径并计算该路径边缘上的数字之和。将所有得到的和写在黑板上。然后从 $$$1$$$ 到 $$$\lfloor \frac{2n^2}{9} \rfloor$$$ 的每个整数都必须至少在黑板上写一次。
保证存在这样的安排。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 节点数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),这意味着节点 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证这些边形成一棵树。
输出
输出 $$$n-1$$$ 行,每行形式为 $$$u$$$ $$$v$$$ $$$x$$$ ($$$0 \le x \le 10^6$$$),这意味着你在 $$$u$$$ 和 $$$v$$$ 之间的边缘写下了数字 $$$x$$$。
边集 $$$(u, v)$$$ 必须与输入图的边集一致,但您可以按任何顺序输出边。您还可以按照与输入顺序不同的顺序输出边的末端。
示例
输入 #1
3 2 3 2 1
输出 #1
3 2 1 1 2 2
输入 #2
4 2 4 2 3 2 1
输出 #2
4 2 1 3 2 2 1 2 3
输入 #3
5 1 2 1 3 1 4 2 5
输出 #3
2 1 1 5 2 1 3 1 3 4 1 6
注意
在第一个示例中,节点 $$$1$$$ 和 $$$2$$$ 之间的距离等于 $$$2$$$,节点 $$$2$$$ 和 $$$3$$$ 之间到 $$$1$$$,$$$1$$$ 和 $$$3$$$ 到 $$$3$$$ 之间的距离等于 $$$3$$$。
在第三个例子中,从$$$1$$$到$$$9$$$(含)的数字将被写在黑板上,而我们只需要从$$$1$$$到$$$5$$$就可以通过测试。