P15993 [PA 2026] Prüfer 序列 / Kod Prüfera

$\large{\bf{\textcolor{red}{警告：滥用本题评测，一次即可封号甚至封禁\ IP。}}}$ $\large{\bf{\textcolor{red}{已有多人因相关行为受到学校处分，切记前人教训。}}}$ 由于评测机性能差异，本题时限下调 $5$ 秒。

给定一棵有 $n$ 个顶点（其中 $n > 2$）的树，顶点编号为 1 到 $n$，其 Prüfer 序列是一个长度为 $n - 2$ 的唯一确定的数列，可以通过以下简单算法得到： 当树的顶点数超过两个时： - 找到编号最小的度为 1 的顶点 - 将其唯一邻居的编号加入序列 - 从树中删除该顶点 可以证明，每个由 1 到 $n$ 之间的数组成的长度为 $n - 2$ 的序列都是某棵树的 Prüfer 序列，并且 Prüfer 序列唯一地确定了它所来源的树。关于 Prüfer 序列的这些以及其他有趣的事实，可参阅 OI-wiki 或其他资料。 在本题中，我们给定一棵树，并考虑由该树顶点的不同编号方式所生成的 Prüfer 序列。若 $S$ 是某种顶点编号方式（即，形式上是从顶点集合到集合 $\{1,\dots,n\}$ 的一个单射函数），则用 $K(S)$ 表示在该编号方式下树的 Prüfer 序列。 你的任务是求给定树的字典序最小的 Prüfer 序列，即存在某种顶点编号方式 $S$ 使得该序列等于 $K(S)$，且对于任意其他顶点编号方式 $S'$，要么 $K(S) = K(S')$，要么在 $K(S)$ 与 $K(S')$ 第一个不同的位置上，$K(S')$ 中的数更大。 你需要对 $t$ 个独立的测试用例求解本题。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示需要求解的测试用例数量。 每个测试用例的描述以一行开始，该行包含一个整数 $n$（$3 \leq n \leq 1000$），表示树的顶点数。树的顶点编号为 1 到 $n$，但此编号不一定对应字典序最小的 Prüfer 序列。 接下来 $n - 1$ 行描述树的边。每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n,\ a_i \neq b_i$），表示顶点 $a_i$ 与顶点 $b_i$ 之间有一条边相连。 所有测试用例的 $n$ 之和不超过 5000。

输出 $t$ 行，每个测试用例对应一行。第 $i$ 行输出一个长度为 $n - 2$ 的数列，即第 $i$ 个测试用例中树在最优顶点编号方式下字典序最小的 Prüfer 序列。

### 样例解释 在第一个测试用例中，给出字典序最小的 Prüfer 序列的顶点编号方案示例为 $1 \to 5$，$2 \to 2$，$3 \to 1$，$4 \to 4$，$5 \to 3$。 对于这样的编号方式，Prüfer 序列求解算法在第一步将选择新编号为 $3$ 的顶点（并将 $1$ 加入序列，即其唯一邻居的新编号）。在第二步中，将选择新编号为 $4$ 的顶点（其唯一邻居同样是 $1$）。在第三步中（删除顶点 $3$ 和 $4$ 后），顶点 $1$ 已成为叶子节点，将被选中，其邻居的编号 $2$ 将作为序列的最后一个元素被加入。 在第二个测试用例中，最优方案是完全不对顶点重新编号，此外，输入中边的顺序与 Prüfer 序列求解算法中删除叶子节点的顺序一致。