1627C.md (2669B)
1 Source: https://codeforces.com/problemset/problem/1627/C 2 3 C. Not Assigning 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 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. 26 27  28 29 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. 30 31 Input 32 33 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. 34 35 The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree. 36 37 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. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 40 41 Output 42 43 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$. 44 45 If there are multiple solutions, you may print any. 46 47 Example 48 49 Input 50 51 ``` 52 3 53 54 2 55 56 1 2 57 58 4 59 60 1 3 61 62 4 3 63 64 2 1 65 66 7 67 68 1 2 69 70 1 3 71 72 3 4 73 74 3 5 75 76 6 2 77 78 7 2 79 ``` 80 81 Output 82 83 ``` 84 17 85 2 5 11 86 -1 87 ``` 88 89 Note 90 91 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. 92 93  94 95 The second test case is described in the statement. 96 97 It can be proven that no such assignment exists for the third test case.