D. 树的重标号
每个测试点时间限制：2 秒
每个测试点内存限制：256 兆字节

Eikooc 和 Sushi 玩一个游戏。

游戏在一棵有 $n$ 个节点的树上进行，节点编号为 $1$ 到 $n$。
（注：一棵 $n$ 个节点的树是无向连通图，有 $n-1$ 条边。）

他们轮流移动棋盘上的一个棋子。Eikooc 先手，她将棋子放在任意一个她选择的节点上。
然后 Sushi 移动棋子，接着 Eikooc 移动，再 Sushi 移动，如此交替。
在第一步之后的每一轮中，当前玩家必须将棋子从当前所在节点 $v$ 移动到满足以下条件的节点 $u$：

• $u$ 与 $v$ 相邻；
• $u$ 之前没有被访问过；
• $u \oplus v \le \min(u, v)$。

这里 $x \oplus y$ 表示整数 $x$ 和 $y$ 的按位异或。

双方都采取最优策略。无法移动的玩家输。

下面的例子展示了游戏规则：

• 假设 Eikooc 将棋子放在节点 $4$。Sushi 将棋子移到节点 $6$，$6$ 未被访问且与 $4$ 相邻，并且 $6 \oplus 4 = 2 \le \min(6, 4)$。接着 Eikooc 将棋子移到节点 $5$，$5$ 未被访问且与 $6$ 相邻，并且 $5 \oplus 6 = 3 \le \min(5, 6)$。Sushi 无法再移动，所以她输了。
• 假设 Eikooc 将棋子放在节点 $3$。Sushi 将棋子移到节点 $2$，$2$ 未被访问且与 $3$ 相邻，并且 $3 \oplus 2 = 1 \le \min(3, 2)$。Eikooc 无法将棋子移到节点 $6$，因为 $6 \oplus 2 = 4 \not\le \min(6, 2)$。由于 Eikooc 无法移动，她输了。

在游戏开始前，Eikooc 偷偷地重新标记树的节点，以便对自己有利。
形式化地说，一个重标号是一个长度为 $n$ 的排列 $p$（包含 $1$ 到 $n$ 每个整数恰好一次），其中 $p_i$ 表示节点 $i$ 的新编号。

她希望最大化她在第一步中选择的节点数量，这些节点能保证她获胜。
帮助 Eikooc 找到任意一个重标号，使她达到这一目标。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。
每个测试用例描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示树的节点数。
• 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示节点 $u$ 和 $v$ 之间有一条边。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出任意一个合适的重标号——一个长度为 $n$ 的排列，使得第一步中能保证 Eikooc 获胜的节点数最大。
如果有多个这样的重标号，输出任意一个即可。

示例
输入：

3
1
2
1 2
3
1 2
1 3

输出：

1
2 1
1 2 3

注意

• 在第一个测试用例中，Eikooc 只有一个选择。她选择这个节点后，Sushi 无法移动，Eikooc 获胜。
• 在第二个测试用例中，$1 \oplus 2 = 3 \not\le \min(1, 2)$。因此，无论 Eikooc 选择哪个节点，Sushi 都无法移动，Eikooc 获胜。重标号 $\{1,2\}$ 和 $\{2,1\}$ 都是最优的。