CF1867F.Most Different Tree

Given a tree with $n$ vertices rooted at vertex $1$, denote it as $G$. Also denote $P(G)$ as the multiset of subtrees of all vertices in tree $G$. You need to find a tree $G'$ of size $n$ rooted at vertex $1$ such that the number of subtrees in $P(G')$ that are isomorphic to any subtree in $P(G)$ is minimized.

A subtree of vertex $v$ is a graph that contains all vertices for which vertex $v$ lies on the path from the root of the tree to itself, as well as all edges between these vertices.

Two rooted trees are considered isomorphic if it is possible to relabel the vertices of one of them so that it becomes equal to the other, with the root of the first tree receiving the number of the root of the second tree.

给定一棵包含 $n$ 个顶点、以顶点 $1$ 为根的树，记作 $G$。再记 $P(G)$ 为树 $G$ 中所有顶点的子树构成的多重集。你需要构造一棵大小为 $n$、以顶点 $1$ 为根的树 $G'$，使得 $P(G')$ 中与 $P(G)$ 中任意子树同构的子树数量最小。

顶点 $v$ 的子树是指：包含所有满足“$v$ 位于从树根到该顶点的路径上”的顶点，以及这些顶点之间所有边所构成的图。

两棵有根树被认为是同构的，当且仅当可以对其中一棵树的顶点重新标号，使其与另一棵树完全相等，且第一棵树的根被标号为第二棵树的根的编号。

The first line contains a single integer $n$ ($2 \le n \le 10^6$) - the number of vertices in tree $G$. Each of the next $n-1$ lines contains two integers $a$ and $b$ $(1 \leq a,b \leq n)$, indicating that there is an edge between vertices $a$ and $b$ in the tree.

第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示树 $G$ 的顶点数。接下来的 $n-1$ 行每行包含两个整数 $a$ 和 $b$（$1 \leq a,b \leq n$），表示树中顶点 $a$ 与顶点 $b$ 之间存在一条边。

Output $n-1$ lines, each line containing two numbers $a$, $b$ $(1 \leq a,b \leq n)$ - the edges of tree $G'$. If there are multiple optimal answers, output any.

输出 $n-1$ 行，每行包含两个数 $a$、$b$ $(1 \leq a,b \leq n)$，表示树 $G'$ 的一条边。若存在多个最优解，输出任意一个即可。