题目描述
你的面前有一棵树。
这棵树共有 $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$ 上的鸽子的编号。
可以证明，一定存在至少一组解。
所有满足要求的输出均可通过。
样例 1 输入
2 3 1 2 1 3 5 4 2 1 5 3 1 2 1
样例 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 1（21 points）：$n \le 8$。
- Subtask 2（25 points）：$n \le 1000$。
- Subtask 3（11 points）：对于任意小于 $n$ 的正整数 $i$，都满足 $u_i=1$ 且 $v_i=i+1$。
- Subtask 4（18 points）：对于任意小于 $n$ 的正整数 $i$，都满足 $u_i=i$ 且 $v_i=i+1$。
- Subtask 5（25 points）：无特殊限制。