Non Prime Tree
Contest: Codeforces Round 992 (Div. 2)
Difficulty rating: 1900
Tags: brute force, constructive algorithms, dfs and similar, greedy, number theory, trees, two pointers

You are given a tree with $$$n$$$ vertices.

You need to construct an array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, consisting of unique integers from $$$1$$$ to $$$2 \cdot n$$$, and such that for each edge $$$u_i \leftrightarrow v_i$$$ of the tree, the value $$$|a_{u_i} - a_{v_i}|$$$ is not a prime number.

Find any array that satisfies these conditions, or report that there is no such array.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The next $$$n - 1$$$ lines contain the edges of the tree, one edge per line. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$), denoting the edge between the nodes $$$u_i$$$ and $$$v_i$$$.

It's guaranteed that the given edges form a tree.

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, if an array that satisfies the conditions exists, print its elements $$$a_1, a_2, \ldots, a_n$$$. Otherwise, print $$$-1$$$.

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

Note:
The possible answers are shown below. Instead of the vertex numbers, the corresponding elements of the array $$$a$$$ are written in them.

The image of the tree in the first test case

The image of the tree in the second test case

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

Example output:
2 10 1 6 5 
8 7 12 1 4 6 3

Editorial:
There are many array construction tactics that can be devised here. We will show two of them.
1. We will perform a depth-first traversal of the graph and write a number $$$1$$$ greater than the previous one in the traversal order into each subsequent vertex. If the next vertex is not a leaf, then some number has already been written into its parent, which may violate the condition "$$$|a_{u_i} - a_{v_i}|$$$ is prime". If the difference is even and not equal to $$$2$$$, then the condition is satisfied. Otherwise, the condition may be satisfied, but we will still achieve an even difference not equal to $$$2$$$. If the difference is odd, first add the number $$$1$$$. If the difference becomes $$$2$$$, add another $$$2$$$. It can be shown that if we added this additional $$$2$$$, then we did not add them to the previous two vertices in the traversal order.
2. We will write the values $$$2, 4, 6, \dots$$$ to the vertices with even depth in breadth-first order. We will write the values $$$n \cdot 2, n \cdot 2 - 2, n \cdot 2 - 4, \dots$$$ to the vertices with odd depth in breadth-first order. In such a traversal, the condition "$$$|a_{u_i} - a_{v_i}|$$$ is prime" can be violated only for one pair, and one of the vertices of this pair will be a leaf. We will change the value of this leaf to the value of the parent minus $$$1$$$.