# [Answer] Hemose on the Tree solution codeforces

## [Answer] Hemose on the Tree solution codeforces

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 nn vertices where nn is a power of 22. You have to give each node and edge an integer value in the range [1,2n1][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 other node or edge is minimized.

The cost of the path between two nodes uu and vv or any node uu and edge ee 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

The first line contains a single integer tt (1t51041≤t≤5⋅104) — the number of test cases. Then tt test cases follow.

The first line of each test case contains a single integer pp (1p171≤p≤17), where nn (the number of vertices in the tree) is equal to 2p2p.

Each of the next n1n−1 lines contains two integers uu and vv (1u,vn1≤u,v≤n) meaning that there is an edge between the vertices uu and vv in the tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of nn over all test cases doesn’t exceed 31053⋅105.

Output

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

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

On the third line, print n1n−1 integers separated by spaces, where the ii-th integer represents the chosen value for the ii-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.

Example

input

Copy
2
2
1 2
2 3
3 4
3
1 2
2 3
3 4
1 5
1 6
5 7
5 8


output

Copy
3
5 1 3 6
4 2 7
5
1 2 8 11 4 13 9 15
6 14 3 7 10 5 12

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:

• 33;
• 37=43⊕7=4;
• 376=23⊕7⊕6=2;
• 32=13⊕2=1;
• 321=03⊕2⊕1=0;
• 3214=43⊕2⊕1⊕4=4;
• 32145=13⊕2⊕1⊕4⊕5=1.

The maximum cost of all these paths is 44. 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: