Eikooc 和 Sushi 玩游戏。
游戏在具有 $$$n$$$ 节点、编号为 $$$1$$$ 到 $$$n$$$ 的树上进行。回想一下,具有 $$$n$$$ 节点的树是具有 $$$n-1$$$ 边的无向连通图。
他们轮流交替移动树上的令牌。 Eikooc 迈出了第一步,将代币放置在她选择的任何节点上。 Sushi 采取下一步行动,Eikooc 紧随其后,Sushi 紧随其后,依此类推。在第一回合之后的每一回合中,玩家必须将代币移动到节点 $$$u$$$,这样
- $$$u$$$ 与令牌当前所在的节点 $$$v$$$ 相邻
- $$$u$$$ 之前未被访问过
- $$$u \oplus v \leq min(u, v)$$$
这里 $$$x \oplus y$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的按位异或运算。
两位选手都发挥最佳。无法采取行动的玩家就输了。
以下是演示游戏规则的示例。
假设 Eikooc 通过将代币放置在节点 $$$4$$$ 来开始游戏。然后,Sushi 将代币移动到节点 $$$6$$$,该节点未被访问且与 $$$4$$$ 相邻。它还成立 $$$6 \oplus 4 = 2 \leq min(6, 4)$$$。在下一回合中,Eikooc 将代币移动到节点 $$$5$$$,该节点未被访问且与 $$$6$$$ 相邻。它认为 $$$5 \oplus 6 = 3 \leq min(5, 6)$$$。寿司没有更多的动作可玩,所以她输了。 假设 Eikooc 通过将代币放置在节点 $$$3$$$ 来开始游戏。 Sushi 将代币移动到节点 $$$2$$$,该节点未被访问且与 $$$3$$$ 相邻。它还成立 $$$3 \oplus 2 = 1 \leq min(3, 2)$$$。 Eikooc 无法将令牌移动到节点 $$$6$$$,因为 $$$6 \oplus 2 = 4 \nleq min(6, 2)$$$。由于 Eikooc 无招可走,她输了。
在游戏开始之前,Eikooc 决定偷偷地以对她有利的方式重新标记树的节点。形式上,重新标记是长度为 $$$n$$$ 的排列 $$$p$$$($$$n$$$ 整数的序列,其中从 $$$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 \neq v)$$$ — 表示节点 $$$u$$$ 和 $$$v$$$ 之间的边。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印任何合适的重新标签 - 长度 $$$n$$$ 的排列,最大化第一回合中可以选择的节点数量,从而保证 Eikooc 获胜。如果有多个此类重新标签,您可以打印其中任何一个。
示例
输入 #1
3 1 2 1 2 3 1 2 1 3
输出 #1
1 2 1 1 2 3
注意
在第一个测试用例中,Eikooc 只有一个选择。 Eikooc 选择此节点后,Sushi 将无棋可走,Eikooc 将获胜。
在第二个测试用例中,$$$1 \oplus 2 = 3 \nleq min(1, 2)$$$。因此,在 Eikooc 选择任一节点后,Sushi 将无棋可走,Eikooc 将获胜。 $$$\{1, 2\}$$$ 和 $$$\{2, 1\}$$$ 都是最佳重新标记。