「Cfz Round 9」Dove

你的面前有一棵树。 这棵树共有 $n$ 个结点，这些结点之间由 $n-1$ 根树枝相连，每个结点上都有一只鸽子。 她希望你对所有鸽子进行编号。设第 $i$ 只鸽子的编号为 $p_i$，你需要满足： - 序列 $p$ 为一个 $1 \sim n$ 的排列，即 $1\sim n$ 中的每个数在所有鸽子的编号中恰好出现一次； - 对于结点 $u,v$，若结点 $u$ 与结点 $v$ 之间存在一根树枝，则结点 $u$ 上的鸽子的编号与结点 $v$ 上的鸽子的编号之和不大于 $n+1$，即 $p_u+p_v \le n+1$。 你想求出一种满足条件的对鸽子进行编号的方式。可以证明，一定存在至少一组解。

**本题有多组测试数据。** 输入的第一行包含一个正整数 $T$，表示测试数据组数。 接下来依次输入每组测试数据。对于每组测试数据： - 第一行一个正整数 $n$。 - 接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$，表示结点 $u_i$ 与结点 $v_i$ 之间存在一根树枝。

对于每组测试数据，输出一行 $n$ 个正整数，其中第 $i$ 个正整数表示你求出的对鸽子进行编号的方式中 $p_i$ 的值，即结点 $i$ 上的鸽子的编号。 可以证明，一定存在至少一组解。 **所有满足要求的输出均可通过。**

2
3
1 2
1 3
5
4 2
1 5
3 1
2 1

1 3 2
1 2 3 4 5

#### 「样例解释 #1」 对于第 $1$ 组测试数据，结点 $1$ 上的鸽子的编号为 $1$，结点 $2$ 上的鸽子的编号为 $3$，结点 $3$ 上的鸽子的编号为 $2$，由于 $1+2$ 和 $1+3$ 均不大于 $4$，所以这种对鸽子进行编号的方式满足条件。 对于第 $2$ 组测试数据，另一种满足条件的对鸽子进行编号的方式为：令结点 $1,2,3,4,5$ 上的鸽子的编号分别为 $2,1,4,5,3$。 #### 「数据范围」 对于所有测试数据，保证： - $1 \le T \le 10$； - $2 \le n \le 10^5$； - $1 \le u_i,v_i \le n$； - 输入数据形成一棵树。 **本题采用捆绑测试。** - Subtask 0（21 points）：$n \le 8$。 - Subtask 1（25 points）：$n \le 1000$。 - Subtask 2（11 points）：对于任意小于 $n$ 的正整数 $i$，都满足 $u_i=1$ 且 $v_i=i+1$。 - Subtask 3（18 points）：对于任意小于 $n$ 的正整数 $i$，都满足 $u_i=i$ 且 $v_i=i+1$。 - Subtask 4（25 points）：无特殊限制。