1899F.md (3375B)
1 Source: https://codeforces.com/problemset/problem/1899/F 2 3 F. Alex's whims 4 5 time limit per test 6 7 1 second 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 Tree is a connected graph without cycles. It can be shown that any tree of $n$ vertices has exactly $n - 1$ edges. 22 23 Leaf is a vertex in the tree with exactly one edge connected to it. 24 25 Distance between two vertices $u$ and $v$ in a tree is the minimum number of edges that must be passed to come from vertex $u$ to vertex $v$. 26 27 Alex's birthday is coming up, and Timofey would like to gift him a tree of $n$ vertices. However, Alex is a very moody boy. Every day for $q$ days, he will choose an integer, denoted by the integer chosen on the $i$-th day by $d_i$. If on the $i$-th day there are not two leaves in the tree at a distance exactly $d_i$, Alex will be disappointed. 28 29 Timofey decides to gift Alex a designer so that he can change his tree as he wants. Timofey knows that Alex is also lazy (a disaster, not a human being), so at the beginning of every day, he can perform no more than one operation of the following kind: 30 31 * Choose vertices $u$, $v_1$, and $v_2$ such that there is an edge between $u$ and $v_1$ and no edge between $u$ and $v_2$. Then remove the edge between $u$ and $v_1$ and add an edge between $u$ and $v_2$. This operation cannot be performed if the graph is no longer a tree after it. 32 33 Somehow Timofey managed to find out all the $d_i$. After that, he had another brilliant idea — just in case, make an instruction manual for the set, one that Alex wouldn't be disappointed. 34 35 Timofey is not as lazy as Alex, but when he saw the integer $n$, he quickly lost the desire to develop the instruction and the original tree, so he assigned this task to you. It can be shown that a tree and a sequence of operations satisfying the described conditions always exist. 36 37  38 39 Here is an example of an operation where vertices were selected: $u$ — $6$, $v_1$ — $1$, $v_2$ — $4$. 40 41 Input 42 43 The first line contains the integer $t$ ($1 \leq t \leq 100$) — the number of test cases. 44 45 The first line of each test case contains two integers $n$ ($3 \leq n \leq 500$) and $q$ ($1 \leq q \leq 500$) — the number of nodes in the tree and the number of days, respectively. 46 47 The $i$th of the following $q$ lines contains the integer $d_i$ ($2 \leq d_i \leq n - 1$). 48 49 It is guaranteed that the sum of $n$ over all test cases does not exceed $500$. The same is guaranteed for $q$. 50 51 It can be shown that a tree and a sequence of operations satisfying the described conditions always exist. 52 53 Output 54 55 For each test case, first print an $n - 1$ string describing the edges of the tree. If you want the tree to have an edge between nodes $u$ and $v$, there must be a string $v$ $u$ or $u$ $v$ among these $n - 1$ lines. 56 57 In the next $q$ lines, print three integers each $u$ $v_1$ $v_2$ — a description of the operations. If Alex doesn't need to perform an operation the following day, print $-1$ $-1$ $-1$. 58 59 Example 60 61 Input 62 63 ``` 64 3 65 66 3 3 67 68 2 69 70 2 71 72 2 73 74 5 6 75 76 4 77 78 2 79 80 3 81 82 4 83 84 3 85 86 2 87 88 4 9 89 90 2 91 92 3 93 94 3 95 96 2 97 98 2 99 100 2 101 102 3 103 104 2 105 106 2 107 ``` 108 109 Output 110 111 ``` 112 1 2 113 2 3 114 -1 -1 -1 115 -1 -1 -1 116 -1 -1 -1 117 1 2 118 2 3 119 3 4 120 4 5 121 -1 -1 -1 122 4 3 2 123 5 4 3 124 4 2 5 125 4 5 2 126 5 3 4 127 1 2 128 2 3 129 3 4 130 4 3 2 131 4 2 3 132 -1 -1 -1 133 4 3 2 134 -1 -1 -1 135 -1 -1 -1 136 4 2 3 137 4 3 2 138 -1 -1 -1 139 ```