Hemose on the Tree
Contest: Codeforces Round 788 (Div. 2)
Difficulty rating: 2200
Tags: bitmasks, constructive algorithms, dfs and similar, trees

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).

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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:

Example input:
2
2
1 2
2 3
3 4
3
1 2
2 3
3 4
1 5
1 6
5 7
5 8

Example output:
3
5 1 3 6
4 2 7
5
1 2 8 11 4 13 9 15
6 14 3 7 10 5 12

Editorial:
Let's look at the minimum maximum value that we can get if we have an array of numbers from $$$[1,2^{(p+1)}-1]$$$ and we are trying to get any prefix xor, the answer will be $$$2^p$$$ because you can stop at the first integer that will have the bit $$$p$$$ so the answer will be $$$\geq 2^p$$$.
We can apply the same concept here, for any arrangement we can start at the root and stop at the first node/edge that has the bit $$$p$$$ on. Let's try to find a construction that will make our answer always $$$2^p$$$. This is one of the valid ways.
1. Select an arbitrary root.
2. Put $$$2^p$$$ at the root.
3. Create $$$2^p-1$$$ pairs from the remaining numbers of the form $$$(x,x+2^p)$$$ where $$$x < 2^p$$$
4. For every node we will do the following:   If its parent has the bit $$$p$$$ in its value the node will take the value $$$x$$$ and the edge to the parent will take $$$x+2^p$$$.  If its parent doesn't have the bit $$$p$$$ in its value the node will take the value $$$x+2^p$$$ and the edge to the parent will take $$$x$$$. Using this construction you will find that the xor value form the root will alternate between $$$0$$$ and $$$2^p$$$ and $$$x$$$ which is always $$$ \le 2^p$$$ .
5. If its parent has the bit $$$p$$$ in its value the node will take the value $$$x$$$ and the edge to the parent will take $$$x+2^p$$$.
6. If its parent doesn't have the bit $$$p$$$ in its value the node will take the value $$$x+2^p$$$ and the edge to the parent will take $$$x$$$.