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.