Most Different Tree

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一棵有 $n$ 个顶点的树 $G$。顶点编号为 $1$ 到 $n$，根为顶点 $1$。

用 $P(G)$ 表示 $G$ 中以每个顶点为根的子树所组成的集合。这里，一个顶点的子树包含该顶点及其所有后代。

请构造另一棵同样有 $n$ 个顶点、根为顶点 $1$ 的树 $G'$，使 $P(G')$ 中与 $P(G)$ 中某棵子树同构的子树数量最少。

两棵有根树同构，当且仅当存在保持父子关系的顶点双射。

如果有多种最优构造，输出任意一种。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $G$ 中顶点 $u$ 与顶点 $v$ 之间有一条边。

输入保证这些边构成一棵树。

输出格式

输出 $n-1$ 行，每行两个整数 $u,v$，表示你构造的树 $G'$ 中的一条边。

输出必须构成一棵以顶点 $1$ 为根、顶点编号为 $1$ 到 $n$ 的树，并且达到最小的匹配子树数量。

样例输入 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
2 4

数据范围

对于所有数据，$2\le n\le 10^6$。

每个测试点独立计分。

说明

样例输出仅为一种可行的最优构造；你的输出可以与样例不同。