codeforces-scrape

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

1798B.md (2950B)


      1 Source: https://codeforces.com/problemset/problem/1798/B
      2 
      3 B. Three Sevens
      4 
      5 time limit per test
      6 
      7 2 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 Lottery "Three Sevens" was held for $m$ days. On day $i$, $n_i$ people with the numbers $a_{i, 1}, \ldots, a_{i, n_i}$ participated in the lottery.
     22 
     23 It is known that in each of the $m$ days, only one winner was selected from the lottery participants. The lottery winner on day $i$ was not allowed to participate in the lottery in the days from $i+1$ to $m$.
     24 
     25 Unfortunately, the information about the lottery winners has been lost. You need to find any possible list of lottery winners on days from $1$ to $m$ or determine that no solution exists.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50\,000$). The description of the test cases follows.
     30 
     31 The first line of each test case contains a single integer $m$ ($1 \le m \le 50\,000$) — the number of days in which the lottery was held.
     32 
     33 Next, for each $i$ from $1$ to $m$, follows a two-line block of data.
     34 
     35 The first line of each block contains a single integer $n_i$ ($1 \le n_i \le 50\,000$) — the number of lottery participants on day $i$.
     36 
     37 The second line of the block contains integers $a_{i, 1}, \ldots, a_{i, n_i}$ ($1 \le a_{i, j} \le 50\,000$) — lottery participants on day $i$. It is guaranteed that all the numbers $a_{i, 1}, \ldots, a_{i, n_i}$ are pairwise distinct.
     38 
     39 It is guaranteed that the sum of $n_i$ over all blocks of all test cases does not exceed $50\,000$.
     40 
     41 Output
     42 
     43 For each test case, if there is no solution, print a single integer $-1$.
     44 
     45 Otherwise, print $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \le p_i \le 50\,000$) — lottery winners on days from $1$ to $m$. If there are multiple solutions, print any of them.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 
     54 3
     55 
     56 4
     57 
     58 1 2 4 8
     59 
     60 3
     61 
     62 2 9 1
     63 
     64 2
     65 
     66 1 4
     67 
     68 2
     69 
     70 2
     71 
     72 1 2
     73 
     74 2
     75 
     76 2 1
     77 
     78 4
     79 
     80 4
     81 
     82 1 2 3 4
     83 
     84 1
     85 
     86 1
     87 
     88 1
     89 
     90 4
     91 
     92 1
     93 
     94 3
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 8 2 1 
    101 -1
    102 2 1 4 3
    103 ```
    104 
    105 Note
    106 
    107 In the first test case, one of the answers is $[8, 2, 1]$ since the participant with the number $8$ participated on day $1$, but did not participate on days $2$ and $3$; the participant with the number $2$ participated on day $2$, but did not participate on day $3$; and the participant with the number $1$ participated on day $3$. Note that this is not the only possible answer, for example, $[8, 9, 4]$ is also a correct answer.
    108 
    109 In the second test case, both lottery participants participated on both days, so any possible lottery winner on the day $1$ must have participated on the day $2$, which is not allowed. Thus, there is no correct answer.
    110 
    111 In the third test case, only one participant participated on days $2$, $3$, $4$, and on day $1$ there is only one participant who did not participate in the lottery on days $2, 3, 4$ — participant $2$, which means $[2, 1, 4, 3]$ is the only correct answer to this test case.