Hemose on the Tree Codeforces Solution | Codeforces Problem Solution 2022

Hemose on the Tree Codeforces Solution | Codeforces Problem Solution 2022

E. Hemose on the Tree

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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$2$. You have to give each node and edge an integer value in the range [1,2𝑛−1]$[1,2n-1]$ (inclusive), where all the values are distinct.

Solution Click Below:-  CLICK HERE

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

Prof. Slim Codeforces Solution | Codeforces Problem Solution 2022

Dorms War Codeforces Solution | Codeforces Problem Solution 2022

Where is the Pizza? Codeforces Solution | Codeforces Problem Solution 2022

Very Suspicious Codeforces Solution | Codeforces Problem Solution 2022

Hemose on the Tree Codeforces Solution | Codeforces Problem Solution 2022

Jee, You See? Codeforces Solution | Codeforces Problem Solution 2022

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤5⋅104$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≤𝑝≤17$1\le p\le 17$), where 𝑛$n$ (the number of vertices in the tree) is equal to 2𝑝$2^p$.

Each of the next 𝑛−1$n-1$ lines contains two integers 𝑢$u$ and 𝑣$v$ (1≤𝑢,𝑣≤𝑛$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⋅105$3\cdot {10}^5$.

Output

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 𝑛−1$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.

Join Now for Solution:-