codeforces-scrape

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

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