codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/976e522c1fcee260bb8ac5db8894f571abb0d26e.png) 
     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  ![](https://espresso.codeforces.com/f657ff3e3934d03fdf02a9d71d6f585c7dd14318.png) 
     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.