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

只要树中还有多于两个顶点： 找到编号最小的度数为 $1$ 的顶点 将该顶点唯一邻居的编号添加到编码中 * 从树中删除该顶点

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

在本题中，我们给定一棵树，并将考虑通过对该树的顶点进行不同编号方式所生成的 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 \le t \le 1000$)，表示需要解决的测试用例数量。

每个测试用例的描述以包含一个整数 $n$ ($3 \le n \le 1000$) 的行开始，表示树中的顶点数。树中的顶点编号为 $1$ 到 $n$，但此编号不一定对应于字典序最小的 Prüfer 编码。

接下来的 $n - 1$ 行描述了树的边。每一行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示顶点 $a_i$ 和 $b_i$ 由一条边连接。

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

输出格式

输出 $t$ 行，每行对应一个测试用例。在第 $i$ 行，输出一个包含 $n - 2$ 个数字的序列，即第 $i$ 个测试用例中树在最优顶点编号下的字典序最小的 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 编码的示例顶点编号为 $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 编码算法中删除叶子的顺序。