给定一棵树,其中 $$$n$$$ 个顶点以顶点 $$$1$$$ 为根,将其表示为 $$$G$$$。还将 $$$P(G)$$$ 表示为树 $$$G$$$ 中所有顶点的子树的多重集。您需要找到一棵大小为 $$$n$$$ 的树 $$$G'$$$,以顶点 $$$1$$$ 为根,使得 $$$P(G')$$$ 中与 $$$P(G)$$$ 中的任何子树同构的子树数量最小化。
顶点 $$$v$$$ 的子树是一个图,其中包含顶点 $$$v$$$ 位于从树根到自身的路径上的所有顶点,以及这些顶点之间的所有边。
如果可以重新标记其中一个树的顶点,使其与另一个树相等,并且第一棵树的根接收第二棵树的根的编号,则认为两棵有根树是同构的。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) - 树 $$$G$$$ 中的顶点数。接下来的 $$$n-1$$$ 行中的每一行都包含两个整数 $$$a$$$ 和 $$$b$$$ $$$(1 \leq a,b \leq n)$$$,表示树中的顶点 $$$a$$$ 和 $$$b$$$ 之间存在一条边。
输出
输出 $$$n-1$$$ 行,每行包含两个数字 $$$a$$$, $$$b$$$ $$$(1 \leq a,b \leq n)$$$ - 树 $$$G'$$$ 的边。如果有多个最优答案,则输出任意一个。
示例
输入 #1
2 1 2
输出 #1
1 2
输入 #2
3 1 2 1 3
输出 #2
1 2 2 3
输入 #3
4 1 2 1 3 3 4
输出 #3
1 2 2 3 3 4