CF1605D.Treelabeling

Eikooc and Sushi play a game.

The game is played on a tree having $n$ nodes numbered $1$ to $n$. Recall that a tree having $n$ nodes is an undirected, connected graph with $n-1$ edges.

They take turns alternately moving a token on the tree. Eikooc makes the first move, placing the token on any node of her choice. Sushi makes the next move, followed by Eikooc, followed by Sushi, and so on. In each turn after the first, a player must move the token to a node $u$ such that

• $u$ is adjacent to the node $v$ the token is currently on
• $u$ has not been visited before
• $u \oplus v \leq min(u, v)$

Here $x \oplus y$ denotes the bitwise XOR operation on integers $x$ and $y$.

Both the players play optimally. The player who is unable to make a move loses.

The following are examples which demonstrate the rules of the game.

Suppose Eikooc starts the game by placing the token at node $4$. Sushi then moves the token to node $6$, which is unvisited and adjacent to $4$. It also holds that $6 \oplus 4 = 2 \leq min(6, 4)$. In the next turn, Eikooc moves the token to node $5$, which is unvisited and adjacent to $6$. It holds that $5 \oplus 6 = 3 \leq min(5, 6)$. Sushi has no more moves to play, so she loses.

Suppose Eikooc starts the game by placing the token at node $3$. Sushi moves the token to node $2$, which is unvisited and adjacent to $3$. It also holds that $3 \oplus 2 = 1 \leq min(3, 2)$. Eikooc cannot move the token to node $6$ since $6 \oplus 2 = 4 \nleq min(6, 2)$. Since Eikooc has no moves to play, she loses.

Before the game begins, Eikooc decides to sneakily relabel the nodes of the tree in her favour. Formally, a relabeling is a permutation $p$ of length $n$ (sequence of $n$ integers wherein each integer from $1$ to $n$ occurs exactly once) where $p_i$ denotes the new numbering of node $i$.

She wants to maximize the number of nodes she can choose in the first turn which will guarantee her a win. Help Eikooc find any relabeling which will help her do so.

Eikooc 和 Sushi 玩一个游戏。

该游戏在一个含有 $n$ 个节点（编号为 $1$ 到 $n$）的树上进行。回忆一下，一个含有 $n$ 个节点的树是一个具有 $n-1$ 条边的无向连通图。

他们轮流在树上移动一个标记（token）。Eikooc 先手，她可将标记放置在任意一个她选择的节点上；接着由 Sushi 移动，然后是 Eikooc，再然后是 Sushi，依此类推。在首步之后的每一轮中，玩家必须将标记移动到一个节点 $u$，使得：

• $u$ 与标记当前所在节点 $v$ 相邻；
• $u$ 尚未被访问过；
• $u \oplus v \leq \min(u, v)$。

其中 $x \oplus y$ 表示整数 $x$ 与 $y$ 的按位异或（XOR）运算。

双方均以最优策略进行游戏。无法进行合法移动的玩家判负。

以下为若干示例，用于说明游戏规则。

假设 Eikooc 首先将标记置于节点 $4$。随后 Sushi 将标记移至节点 $6$：该节点未被访问过，且与 $4$ 相邻；同时满足 $6 \oplus 4 = 2 \leq \min(6, 4)$。接下来，Eikooc 将标记移至节点 $5$：该节点未被访问过，且与 $6$ 相邻；同时满足 $5 \oplus 6 = 3 \leq \min(5, 6)$。此时 Sushi 已无合法移动，因此她输掉游戏。

假设 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 找出任意一种满足该目标的重标号方案。

The first line contains a single integer $t~(1 \le t \le 10^5)$ — the number of test cases. The description of each test case is as follows.

The first line of each test case contains an integer $n~(1 \le n \le 2 \cdot 10^5)$ — the number of nodes in the tree.

The next $n-1$ lines contain two integers $u$ and $v$ $(1 \le u, v \le n; u \neq v)$ — denoting an edge between nodes $u$ and $v$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case print any suitable relabeling — a permutation of length $n$ which maximizes the number of nodes that can be chosen in the first turn that guarantee a win for Eikooc. If there are multiple such relabelings, you may print any of them.

对于每个测试用例，输出任意一个合适的重标号方案——即一个长度为 $n$ 的排列，使得在第一轮中能够选择并保证 Eikooc 获胜的节点数量最大化。如果存在多个满足条件的重标号方案，输出其中任意一个即可。

In the first test case, Eikooc has only one choice. Sushi will have no moves to play after Eikooc chooses this node and Eikooc will win.

In the second test case, $1 \oplus 2 = 3 \nleq min(1, 2)$. Hence, after Eikooc picks either of the nodes, Sushi will have no moves to play and Eikooc will win. Both ${1, 2}$ and ${2, 1}$ are optimal relabelings.

在第一个测试用例中，Eikooc 只有一种选择。当 Eikooc 选择该节点后，Sushi 将无法进行任何操作，因此 Eikooc 获胜。

在第二个测试用例中，$1 \oplus 2 = 3 \nleq min(1, 2)$。因此，无论 Eikooc 选择哪个节点，Sushi 都将无法进行任何操作，Eikooc 获胜。${1, 2}$ 和 ${2, 1}$ 均为最优重标号方案。