题目描述

你的面前有一棵树。

这棵树共有 $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）：无特殊限制。