CF1670E.Hemose on the Tree

After the last regional contest, Hemose and his teammates finally qualified to the ICPC World Finals, so for this great achievement and his love of trees, he gave you this problem as the name of his team "Hemose 3al shagra" (Hemose on the tree).

You are given a tree of $n$ vertices where $n$ is a power of $2$. You have to give each node and edge an integer value in the range $[1,2n -1]$ (inclusive), where all the values are distinct.

After giving each node and edge a value, you should select some root for the tree such that the maximum cost of any simple path starting from the root and ending at any node or edge is minimized.

The cost of the path between two nodes $u$ and $v$ or any node $u$ and edge $e$ is defined as the bitwise XOR of all the node's and edge's values between them, including the endpoints (note that in a tree there is only one simple path between two nodes or between a node and an edge).

在上一次区域赛之后，Hemose 与其队友成功晋级 ICPC 全球总决赛。为庆祝这一伟大成就，并出于他对树结构的热爱，他将此题作为其队伍名称“Hemose 3al shagra”（Hemose 在树上）献给你。

你将得到一棵包含 $n$ 个顶点的树，其中 $n$ 是 $2$ 的幂。你需要为每个顶点和每条边分配一个 $[1,2n -1]$ 范围内的整数值（含端点），且所有分配的值互不相同。

在为每个顶点和每条边赋值后，你需要为该树选定某个根节点，使得从该根节点出发、终止于任意顶点或任意边的所有简单路径中，最大路径代价最小化。

路径的代价定义如下：对于两个顶点 $u$ 和 $v$，或一个顶点 $u$ 与一条边 $e$，其路径代价为该路径上所有顶点与边所赋值的按位异或（bitwise XOR）结果（包含端点；注意，在树中任意两顶点之间，或任意顶点与边之间，均仅存在唯一一条简单路径）。

The first line contains a single integer $t$ ($1 \le t \le 5\cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains a single integer $p$ ($1 \le p \le 17$), where $n$ (the number of vertices in the tree) is equal to $2^p$.

Each of the next $n−1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$) meaning that there is an edge between the vertices $u$ and $v$ in the tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3\cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 5\cdot 10^4$），表示测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $p$（$1 \le p \le 17$），其中树的顶点数 $n$ 等于 $2^p$。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n$），表示树中顶点 $u$ 与 $v$ 之间存在一条边。

保证所给图是一棵树。

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

For each test case on the first line print the chosen root.

On the second line, print $n$ integers separated by spaces, where the $i$-th integer represents the chosen value for the $i$-th node.

On the third line, print $n-1$ integers separated by spaces, where the $i$-th integer represents the chosen value for the $i$-th edge. The edges are numerated in the order of their appearance in the input data.

If there are multiple solutions, you may output any.

对于每个测试用例，第一行输出所选的根节点。

第二行输出 $n$ 个由空格分隔的整数，其中第 $i$ 个整数表示第 $i$ 个节点所选的值。

第三行输出 $n-1$ 个由空格分隔的整数，其中第 $i$ 个整数表示第 $i$ 条边所选的值。边的编号顺序与其在输入数据中出现的顺序一致。

若存在多个解，输出任意一个即可。

The tree in the first test case with the weights of all nodes and edges is shown in the picture.

The costs of all paths are:

• $3$;
• $3\oplus 7=4$;
• $3\oplus 7\oplus 6=2$;
• $3\oplus 2=1$;
• $3\oplus 2\oplus 1=0$;
• $3\oplus 2\oplus 1\oplus 4=4$;
• $3\oplus 2\oplus 1\oplus 4\oplus 5=1$.

The maximum cost of all these paths is $4$. We can show that it is impossible to assign the values and choose the root differently to achieve a smaller maximum cost of all paths.

The tree in the second test case:

第一个测试用例中的树，其所有节点和边的权重如图所示。

所有路径的代价为：

• $3$；
• $3\oplus 7=4$；
• $3\oplus 7\oplus 6=2$；
• $3\oplus 2=1$；
• $3\oplus 2\oplus 1=0$；
• $3\oplus 2\oplus 1\oplus 4=4$；
• $3\oplus 2\oplus 1\oplus 4\oplus 5=1$。

上述所有路径中最大的代价为 $4$。可以证明：无论怎样重新分配各值或选择不同的根节点，都不可能使所有路径的最大代价小于 $4$。

第二个测试用例中的树：