← 返回题目列表

Codeforces · 1867/F

F. 最不同的树

中文机器翻译题面 查看原题

给定一棵树,其中 $$$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