# Not Assigning solution codeforces

Not Assigning solution codeforces – You are given a tree of 𝑛n vertices numbered from 11 to 𝑛n, with edges numbered from 11 to 𝑛1n−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.

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: 2132→1→3 has a weight of 11+2=1311+2=13, which is prime. Similarly, the path of one edge: 434→3 has a weight of 55, 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−1. It can be proven that if a valid assignment exists, one exists with weights between 11 and 105105 as well.

## Not Assigning solution codeforces Input

The input consists of multiple test cases. The first line contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer 𝑛n (2𝑛1052≤n≤105) — the number of vertices in the tree.

Then, 𝑛1n−1 lines follow. The 𝑖i-th line contains two integers 𝑢u and 𝑣v (1𝑢,𝑣𝑛1≤u,v≤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 105105.

Output

For each test case, if a valid assignment exists, then print a single line containing 𝑛1n−1 integers 𝑎1,𝑎2,,𝑎𝑛1a1,a2,…,an−1 (1𝑎𝑖1051≤ai≤105), where 𝑎𝑖ai denotes the weight assigned to the edge numbered 𝑖i. Otherwise, print 1−1.

If there are multiple solutions, you may print any.

Example
input

Copy
3
2
1 2
4
1 3
4 3
2 1
7
1 2
1 3
3 4
3 5
6 2
7 2


## output Not Assigning solution codeforces

17
2 5 11
-1
Note

For the first test case, there are only two paths having one edge each: 121→2 and 212→1, both having a weight of 1717, 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.