Treelabeling
Contest: Codeforces Round 754 (Div. 2)
Difficulty rating: 2100
Tags: bitmasks, constructive algorithms, dfs and similar, games, greedy, implementation, trees

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.

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

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

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

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

Example input:
3
1
2
1 2
3
1 2
1 3

Example output:
1
2 1
1 2 3

Editorial:
If the most significant bits (MSBs) of two integers $$$x$$$ and $$$y$$$ are the same, say $$$\mathrm{MSB}_x = \mathrm{MSB}_y = b$$$, then the $$$b$$$-th bit will be unset in $$$x \oplus y$$$. Since $$$min(x, y)$$$ will have this bit set, it will be greater than $$$x \oplus y$$$. Thus, if $$$\mathrm{MSB}_x = \mathrm{MSB}_y$$$ then $$$x \oplus y \leq min(x, y)$$$.
If a node in the tree is adjacent only to nodes whose MSB differs from its MSB, then the player who plays this node will win.
It turns out that not only is it always possible to make it such that no two nodes sharing an edge have the same MSB, it is also necessary to do so in order to maximize the number of winnning starting nodes for Eikooc. Consequently, starting at any node will guarantee a win for her.
Why is it necessary if it is always possible? $$$ \\ $$$ Assume there exists at least two nodes in the tree that are adjacent to each other, having the same MSB. We prove that there will be at least one losing node for Eikooc to start on, which is suboptimal. $$$ \\ $$$ Consider a connected component of nodes in the tree of size at least two, all having the same MSB. Since this connected component also forms a tree, it must have at least one leaf node. Any node in the component which is adjacent to at least one of these leaf nodes will be losing for Eikooc (since Sushi can just move the token to a leaf node and Eikooc will have no moves to play).
How do you construct it and is it always possible to do so (if so, why)? $$$ \\ $$$ We aim to relabel the nodes of the tree in such a way that for every node $$$v$$$ in the tree and all nodes $$$u$$$ adjacent to it, $$$\mathrm{MSB}_v \neq \mathrm{MSB}_u$$$. $$$ \\ $$$ Think bipartite. In the bipartite colouring of a tree, no two adjacent nodes have the same colour. If we are able to relabel the nodes in such a way that all nodes with the same MSB belong to the same colour, we are done. $$$ \\ $$$ Key observation: There are $$$2^i$$$ occurrences of integers from $$$1$$$ to $$$n$$$ with the $$$i$$$-th bit as MSB (0-indexed) for each $$$i$$$ from $$$0$$$ to $$$\mathrm{MSB}_n - 1$$$, and all such groups of integers are disjoint (since each integer has exactly one MSB). $$$ \\ $$$ Let the number of white and black nodes be $$$w$$$ and $$$b$$$ respectively and WLOG let $$$w \leq b$$$ (we can swap the colours otherwise). Since all nodes are coloured either white or black, $$$w + b = n$$$. Under these constraints, it is then easy to show that $$$w \leq \frac{n}{2}$$$. Consequently, $$$\mathrm{MSB}_w \lt \mathrm{MSB}_n$$$. Since $$$\mathrm{MSB}_w \lt \mathrm{MSB}_n$$$, $$$w$$$ can possibly only have those bits set which lie in the range $$$[0, \mathrm{MSB}_n - 1]$$$. Can you connect the dots? $$$ \\ $$$ Consider the binary representation of $$$w$$$. We can assign all integers from $$$1$$$ to $$$n$$$ having the $$$i$$$-th bit as MSB to a white node if the $$$i$$$-th bit is set in $$$w$$$, and assign all the remaining integers to black nodes. In doing so, no two nodes having the same MSB will belong to different colours. This ensures that no such pair is adjacent. This is also guaranteed to always be possible since the binary representation of $$$w$$$ only spans the first $$$\mathrm{MSB}_n - 1$$$ bits and we also have access to groups of sizes comprising all powers of two upto $$$\mathrm{MSB}_n - 1$$$.
Time complexity: $$$\mathcal{O}(n)$$$