A14811. Not Assigning

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.

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

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.

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.