Not Assigning
Contest: Codeforces Round 766 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, dfs and similar, number theory, trees

You are given a tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, with edges numbered from $$$1$$$ to $$$n-1$$$. A tree is a connected undirected graph without cycles. You have to assign integer weights to each edge of the tree, such that the resultant graph is a prime tree.

A prime tree is a tree where the weight of every path consisting of one or two edges is prime. A path should not visit any vertex twice. The weight of a path is the sum of edge weights on that path.

Consider the graph below. It is a prime tree as the weight of every path of two or less edges is prime. For example, the following path of two edges: $$$2 \to 1 \to 3$$$ has a weight of $$$11 + 2 = 13$$$, which is prime. Similarly, the path of one edge: $$$4 \to 3$$$ has a weight of $$$5$$$, which is also prime.

Print any valid assignment of weights such that the resultant tree is a prime tree. If there is no such assignment, then print $$$-1$$$. It can be proven that if a valid assignment exists, one exists with weights between $$$1$$$ and $$$10^5$$$ as well.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

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

Then, $$$n-1$$$ lines follow. The $$$i$$$-th line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) denoting that edge number $$$i$$$ is between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, if a valid assignment exists, then print a single line containing $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \leq a_i \le 10^5$$$), where $$$a_i$$$ denotes the weight assigned to the edge numbered $$$i$$$. Otherwise, print $$$-1$$$.

If there are multiple solutions, you may print any.

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

Note:
For the first test case, there are only two paths having one edge each: $$$1 \to 2$$$ and $$$2 \to 1$$$, both having a weight of $$$17$$$, which is prime.

The second test case is described in the statement.

It can be proven that no such assignment exists for the third test case.

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

Example output:
17
2 5 11
-1

Editorial:
Let us first see when a valid assignment does not exist.
Claim. If any vertex has 3 or more edges adjacent to it, no valid assignment exists.
Proof. Consider a graph where a vertex has edges to three other vertices with weights $$$x$$$, $$$y$$$ and $$$z$$$ respectively. For a valid assignment, $$$x$$$, $$$y$$$ and $$$z$$$ need to be primes themselves. Also, $$$x+y$$$, $$$y+z$$$ and $$$x + z$$$ need to be primes too.
Since $$$x, y, z \ge 2$$$ (as $$$2$$$ is the smallest prime), thus $$$x + y, x + z, y + z \ge 4$$$, so they must be odd primes. This implies:
• $$$x$$$ and $$$y$$$ have opposite parity.
• $$$y$$$ and $$$z$$$ have opposite parity.
• $$$x$$$ and $$$z$$$ have opposite parity.
As all the three conditions cannot hold together, hence we have a contradiction.
Proven.
So, we have a tree where every vertex has either one or two edges adjacent to it. Such a tree will have exactly two leaf nodes for $$$n \ge 2$$$ and have the following structure, where $$$V_1$$$ and $$$V_n$$$ are the leaf nodes.
$$$V_1 \longleftrightarrow V_2 \longleftrightarrow V_3 \dots \longleftrightarrow V_{n-1} \longleftrightarrow V_n $$$
Thus, starting a DFS from any leaf node, we can assign weights $$$2$$$ and $$$3$$$ (or $$$2$$$ and the first number of any twin prime pair) alternatingly to form a prime tree, as $$$2$$$, $$$3$$$ and $$$2+3 = 5$$$ are all primes.
Expected time complexity: $$$\mathcal{O}(n)$$$