[AdditionalFile5691.zip](file://AdditionalFile5691.zip?type=additional_file)

#5691. 「PA 2026」Kod Prüfera

标签: 传统 | 时间限制: 25000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 5 Kod Prüfera

对于一棵拥有 $n$ 个顶点的树（其中 $n > 2$），顶点编号从 $1$ 到 $n$，其 Prüfer 编码是一个唯一确定的长度为 $n-2$ 的数字序列，可以通过以下简单算法获得：

当树有超过两个顶点时：
    找到编号最小的度为 1 的顶点
    将该顶点的唯一邻居的编号加入编码
    从树中移除该顶点

可以证明，任何由 $1$ 到 $n$ 之间的数字组成的长度为 $n-2$ 的序列都是某棵树的 Prüfer 编码，且 Prüfer 编码唯一确定了其对应的树。关于 Prüfer 编码的这些事实以及其他有趣的结论，可以在维基百科等资料中找到。

在本题中，我们给定了一棵树，并考虑通过不同方式给树的顶点编号所生成的 Prüfer 编码。如果 $S$ 是一种顶点编号方式（形式上，是从顶点集合到集合 $\{1, \ldots, n\}$ 的双射函数），我们用 $K(S)$ 表示具有此编号方式的树的 Prüfer 编码。

你的任务是确定给定树的字典序最小的 Prüfer 编码，即对于某种编号方式 $S$，序列 $K(S)$ 是所有可能编号方式 $S^{\prime}$ 中字典序最小的。这意味着对于任意其他编号方式 $S^{\prime}$，要么 $K(S) = K(S^{\prime})$，要么在 $K(S)$ 和 $K(S^{\prime})$ 第一个不同的位置上，$K(S)$ 中的数字小于 $K(S^{\prime})$ 中的数字。

你需要为 $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 编码。

样例

输入

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 2
1 1 1 2 2 3 4 3 5 5 3 1 6 7

在第一个测试用例中，使得 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 编码算法中删除叶子节点的顺序。