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.