#216041. [PA 2026] Prüfer 序列 / Kod Prüfera

由于评测机性能差异，本题时限下调 秒。

给定一棵有 个顶点（其中 ）的树，顶点编号为 1 到 ，其 Prüfer 序列是一个长度为 的唯一确定的数列，可以通过以下简单算法得到：

当树的顶点数超过两个时：

• 找到编号最小的度为 1 的顶点
• 将其唯一邻居的编号加入序列
• 从树中删除该顶点

可以证明，每个由 1 到 之间的数组成的长度为 的序列都是某棵树的 Prüfer 序列，并且 Prüfer 序列唯一地确定了它所来源的树。关于 Prüfer 序列的这些以及其他有趣的事实，可参阅 OI-wiki 或其他资料。

在本题中，我们给定一棵树，并考虑由该树顶点的不同编号方式所生成的 Prüfer 序列。若 是某种顶点编号方式（即，形式上是从顶点集合到集合 的一个单射函数），则用 表示在该编号方式下树的 Prüfer 序列。

你的任务是求给定树的字典序最小的 Prüfer 序列，即存在某种顶点编号方式 使得该序列等于 ，且对于任意其他顶点编号方式 ，要么 ，要么在 与 第一个不同的位置上， 中的数更大。

你需要对 个独立的测试用例求解本题。

输入的第一行包含一个整数 （），表示需要求解的测试用例数量。

每个测试用例的描述以一行开始，该行包含一个整数 （），表示树的顶点数。树的顶点编号为 1 到 ，但此编号不一定对应字典序最小的 Prüfer 序列。

接下来 行描述树的边。每行包含两个整数 和 （），表示顶点 与顶点 之间有一条边相连。

所有测试用例的 之和不超过 5000。

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

样例输入 1

2
5
1 2
2 3
3 4
3 5
16
8 1
9 1
10 1
11 2
12 2
2 3
13 4
4 3
14 5
15 5
5 3
3 1
1 6
6 7
7 16

样例输出 1

1 1 2
1 1 1 2 2 3 4 3 5 5 3 1 6 7

样例解释

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