Table of Contents

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

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→1→32→1→3 has a weight of 11+2=1311+2=13, which is prime. Similarly, the path of one edge: 4→34→3 has a weight of 55, which is also prime.

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

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.

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

For the first test case, there are only two paths having one edge each: 1→21→2 and 2→12→1, both having a weight of 1717, which is prime.

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