310223: CF1798B. Three Sevens
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Three Sevens
题意翻译
一共有 $m$ 天,每天有 $n_i$ 人买了彩票,分别为 $a_{i,1} \dots a_{i,{n_i}}$。现在请你安排每天的一位中奖的人,满足他在之后的天里都没有买彩票。如果可以,给出方案,否则输出 $-1$;题目描述
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. 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 $ . 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.输入输出格式
输入格式
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. 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. Next, for each $ i $ from $ 1 $ to $ m $ , follows a two-line block of data. 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 $ . 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. It is guaranteed that the sum of $ n_i $ over all blocks of all test cases does not exceed $ 50\,000 $ .
输出格式
For each test case, if there is no solution, print a single integer $ -1 $ . 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.
输入输出样例
输入样例 #1
3
3
4
1 2 4 8
3
2 9 1
2
1 4
2
2
1 2
2
2 1
4
4
1 2 3 4
1
1
1
4
1
3
输出样例 #1
8 2 1
-1
2 1 4 3
说明
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. 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. 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.Input
题意翻译
一共有 $m$ 天,每天有 $n_i$ 人买了彩票,分别为 $a_{i,1} \dots a_{i,{n_i}}$。现在请你安排每天的一位中奖的人,满足他在之后的天里都没有买彩票。如果可以,给出方案,否则输出 $-1$;Output
**题意翻译**
- 一共有 $m$ 天,每天有 $n_i$ 人买了彩票,分别为 $a_{i,1} \dots a_{i,{n_i}}$。现在请你安排每天的一位中奖的人,满足他在之后的天里都没有买彩票。如果可以,给出方案,否则输出 $-1$。
**题目描述**
- "Three Sevens"彩票进行了 $m$ 天。在第 $i$ 天,有 $n_i$ 人参与了彩票,他们的号码是 $a_{i, 1}, \ldots, a_{i, n_i}$。
- 已知在每天的彩票中只有一个中奖者被选出。第 $i$ 天的中奖者在从第 $i+1$ 天到第 $m$ 天不能参与彩票。
- 不幸的是,关于彩票中奖者的信息已经丢失。你需要找出从第 $1$ 天到第 $m$ 天的可能的中奖者名单,或者确定不存在解决方案。
**输入输出格式**
- **输入格式**:
- 每个测试包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 50,000$)。
- 每个测试用例的第一行包含一个整数 $m$($1 \le m \le 50,000$)——彩票进行的天数。
- 接下来,对于每个 $i$ 从 $1$ 到 $m$,有一个两行的数据块。
- 每个数据块的第一行包含一个整数 $n_i$($1 \le n_i \le 50,000$)——第 $i$ 天的彩票参与者人数。
- 每个数据块的第二天包含整数 $a_{i, 1}, \ldots, a_{i, n_i}$($1 \le a_{i, j} \le 50,000$)——第 $i$ 天的彩票参与者。保证所有的数字 $a_{i, 1}, \ldots, a_{i, n_i}$ 都是两两不同的。
- 保证所有测试用例中所有数据块的 $n_i$ 之和不超过 $50,000$。
- **输出格式**:
- 对于每个测试用例,如果不存在解决方案,则打印一个整数 $-1$。
- 否则,打印 $m$ 个整数 $p_1, p_2, \ldots, p_m$($1 \le p_i \le 50,000$)——从第 $1$ 天到第 $m$ 天的彩票中奖者。如果有多个解决方案,则打印其中任何一个。
**输入输出样例**
- **输入样例 #1**:
```
3
3
4
1 2 4 8
3
2 9 1
2
1 4
2
2
1 2
2
2 1
4
4
1 2 3 4
1
1
1
4
1
3
```
- **输出样例 #1**:
```
8 2 1
-1
2 1 4 3
```
- **说明**:
- 在第一个测试用例中,一个可能的答案是 $[8, 2, 1]$,因为编号为 $8$ 的参与者在第 $1$ 天参与了彩票,但在第 $2$ 天和第 $3$ 天没有参与;编号为 $2$ 的参与者在第 $2$ 天参与了彩票,但在第 $3$ 天没有参与;编号为 $1$ 的参与者在第 $3$ 天参与了彩票。需要注意的是,这不是唯一的答案,例如,$[8, 9, 4]$ 也是正确的答案。
- 在第二个测试用例中,两个彩票参与者在两天都参与了,所以第 $1$ 天的任何可能的中奖者都必须在第 $2$ 天参与过彩票,这是不允许的。因此,没有正确的答案。
- 在第三个测试用例中,只有一位参与者在第 $2$、$3$、$4$ 天参与了彩票,而在第 $1$ 天只有一位参与者没有在第 $2, 3, 4$ 天参与彩票——编号为 $2$ 的参与者,这意味着 $[2, 1, 4, 3]$ 是这个测试用例的唯一正确答案。**题意翻译** - 一共有 $m$ 天,每天有 $n_i$ 人买了彩票,分别为 $a_{i,1} \dots a_{i,{n_i}}$。现在请你安排每天的一位中奖的人,满足他在之后的天里都没有买彩票。如果可以,给出方案,否则输出 $-1$。 **题目描述** - "Three Sevens"彩票进行了 $m$ 天。在第 $i$ 天,有 $n_i$ 人参与了彩票,他们的号码是 $a_{i, 1}, \ldots, a_{i, n_i}$。 - 已知在每天的彩票中只有一个中奖者被选出。第 $i$ 天的中奖者在从第 $i+1$ 天到第 $m$ 天不能参与彩票。 - 不幸的是,关于彩票中奖者的信息已经丢失。你需要找出从第 $1$ 天到第 $m$ 天的可能的中奖者名单,或者确定不存在解决方案。 **输入输出格式** - **输入格式**: - 每个测试包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 50,000$)。 - 每个测试用例的第一行包含一个整数 $m$($1 \le m \le 50,000$)——彩票进行的天数。 - 接下来,对于每个 $i$ 从 $1$ 到 $m$,有一个两行的数据块。 - 每个数据块的第一行包含一个整数 $n_i$($1 \le n_i \le 50,000$)——第 $i$ 天的彩票参与者人数。 - 每个数据块的第二天包含整数 $a_{i, 1}, \ldots, a_{i, n_i}$($1 \le a_{i, j} \le 50,000$)——第 $i$ 天的彩票参与者。保证所有的数字 $a_{i, 1}, \ldots, a_{i, n_i}$ 都是两两不同的。 - 保证所有测试用例中所有数据块的 $n_i$ 之和不超过 $50,000$。 - **输出格式**: - 对于每个测试用例,如果不存在解决方案,则打印一个整数 $-1$。 - 否则,打印 $m$ 个整数 $p_1, p_2, \ldots, p_m$($1 \le p_i \le 50,000$)——从第 $1$ 天到第 $m$ 天的彩票中奖者。如果有多个解决方案,则打印其中任何一个。 **输入输出样例** - **输入样例 #1**: ``` 3 3 4 1 2 4 8 3 2 9 1 2 1 4 2 2 1 2 2 2 1 4 4 1 2 3 4 1 1 1 4 1 3 ``` - **输出样例 #1**: ``` 8 2 1 -1 2 1 4 3 ``` - **说明**: - 在第一个测试用例中,一个可能的答案是 $[8, 2, 1]$,因为编号为 $8$ 的参与者在第 $1$ 天参与了彩票,但在第 $2$ 天和第 $3$ 天没有参与;编号为 $2$ 的参与者在第 $2$ 天参与了彩票,但在第 $3$ 天没有参与;编号为 $1$ 的参与者在第 $3$ 天参与了彩票。需要注意的是,这不是唯一的答案,例如,$[8, 9, 4]$ 也是正确的答案。 - 在第二个测试用例中,两个彩票参与者在两天都参与了,所以第 $1$ 天的任何可能的中奖者都必须在第 $2$ 天参与过彩票,这是不允许的。因此,没有正确的答案。 - 在第三个测试用例中,只有一位参与者在第 $2$、$3$、$4$ 天参与了彩票,而在第 $1$ 天只有一位参与者没有在第 $2, 3, 4$ 天参与彩票——编号为 $2$ 的参与者,这意味着 $[2, 1, 4, 3]$ 是这个测试用例的唯一正确答案。
- 一共有 $m$ 天,每天有 $n_i$ 人买了彩票,分别为 $a_{i,1} \dots a_{i,{n_i}}$。现在请你安排每天的一位中奖的人,满足他在之后的天里都没有买彩票。如果可以,给出方案,否则输出 $-1$。
**题目描述**
- "Three Sevens"彩票进行了 $m$ 天。在第 $i$ 天,有 $n_i$ 人参与了彩票,他们的号码是 $a_{i, 1}, \ldots, a_{i, n_i}$。
- 已知在每天的彩票中只有一个中奖者被选出。第 $i$ 天的中奖者在从第 $i+1$ 天到第 $m$ 天不能参与彩票。
- 不幸的是,关于彩票中奖者的信息已经丢失。你需要找出从第 $1$ 天到第 $m$ 天的可能的中奖者名单,或者确定不存在解决方案。
**输入输出格式**
- **输入格式**:
- 每个测试包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 50,000$)。
- 每个测试用例的第一行包含一个整数 $m$($1 \le m \le 50,000$)——彩票进行的天数。
- 接下来,对于每个 $i$ 从 $1$ 到 $m$,有一个两行的数据块。
- 每个数据块的第一行包含一个整数 $n_i$($1 \le n_i \le 50,000$)——第 $i$ 天的彩票参与者人数。
- 每个数据块的第二天包含整数 $a_{i, 1}, \ldots, a_{i, n_i}$($1 \le a_{i, j} \le 50,000$)——第 $i$ 天的彩票参与者。保证所有的数字 $a_{i, 1}, \ldots, a_{i, n_i}$ 都是两两不同的。
- 保证所有测试用例中所有数据块的 $n_i$ 之和不超过 $50,000$。
- **输出格式**:
- 对于每个测试用例,如果不存在解决方案,则打印一个整数 $-1$。
- 否则,打印 $m$ 个整数 $p_1, p_2, \ldots, p_m$($1 \le p_i \le 50,000$)——从第 $1$ 天到第 $m$ 天的彩票中奖者。如果有多个解决方案,则打印其中任何一个。
**输入输出样例**
- **输入样例 #1**:
```
3
3
4
1 2 4 8
3
2 9 1
2
1 4
2
2
1 2
2
2 1
4
4
1 2 3 4
1
1
1
4
1
3
```
- **输出样例 #1**:
```
8 2 1
-1
2 1 4 3
```
- **说明**:
- 在第一个测试用例中,一个可能的答案是 $[8, 2, 1]$,因为编号为 $8$ 的参与者在第 $1$ 天参与了彩票,但在第 $2$ 天和第 $3$ 天没有参与;编号为 $2$ 的参与者在第 $2$ 天参与了彩票,但在第 $3$ 天没有参与;编号为 $1$ 的参与者在第 $3$ 天参与了彩票。需要注意的是,这不是唯一的答案,例如,$[8, 9, 4]$ 也是正确的答案。
- 在第二个测试用例中,两个彩票参与者在两天都参与了,所以第 $1$ 天的任何可能的中奖者都必须在第 $2$ 天参与过彩票,这是不允许的。因此,没有正确的答案。
- 在第三个测试用例中,只有一位参与者在第 $2$、$3$、$4$ 天参与了彩票,而在第 $1$ 天只有一位参与者没有在第 $2, 3, 4$ 天参与彩票——编号为 $2$ 的参与者,这意味着 $[2, 1, 4, 3]$ 是这个测试用例的唯一正确答案。**题意翻译** - 一共有 $m$ 天,每天有 $n_i$ 人买了彩票,分别为 $a_{i,1} \dots a_{i,{n_i}}$。现在请你安排每天的一位中奖的人,满足他在之后的天里都没有买彩票。如果可以,给出方案,否则输出 $-1$。 **题目描述** - "Three Sevens"彩票进行了 $m$ 天。在第 $i$ 天,有 $n_i$ 人参与了彩票,他们的号码是 $a_{i, 1}, \ldots, a_{i, n_i}$。 - 已知在每天的彩票中只有一个中奖者被选出。第 $i$ 天的中奖者在从第 $i+1$ 天到第 $m$ 天不能参与彩票。 - 不幸的是,关于彩票中奖者的信息已经丢失。你需要找出从第 $1$ 天到第 $m$ 天的可能的中奖者名单,或者确定不存在解决方案。 **输入输出格式** - **输入格式**: - 每个测试包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 50,000$)。 - 每个测试用例的第一行包含一个整数 $m$($1 \le m \le 50,000$)——彩票进行的天数。 - 接下来,对于每个 $i$ 从 $1$ 到 $m$,有一个两行的数据块。 - 每个数据块的第一行包含一个整数 $n_i$($1 \le n_i \le 50,000$)——第 $i$ 天的彩票参与者人数。 - 每个数据块的第二天包含整数 $a_{i, 1}, \ldots, a_{i, n_i}$($1 \le a_{i, j} \le 50,000$)——第 $i$ 天的彩票参与者。保证所有的数字 $a_{i, 1}, \ldots, a_{i, n_i}$ 都是两两不同的。 - 保证所有测试用例中所有数据块的 $n_i$ 之和不超过 $50,000$。 - **输出格式**: - 对于每个测试用例,如果不存在解决方案,则打印一个整数 $-1$。 - 否则,打印 $m$ 个整数 $p_1, p_2, \ldots, p_m$($1 \le p_i \le 50,000$)——从第 $1$ 天到第 $m$ 天的彩票中奖者。如果有多个解决方案,则打印其中任何一个。 **输入输出样例** - **输入样例 #1**: ``` 3 3 4 1 2 4 8 3 2 9 1 2 1 4 2 2 1 2 2 2 1 4 4 1 2 3 4 1 1 1 4 1 3 ``` - **输出样例 #1**: ``` 8 2 1 -1 2 1 4 3 ``` - **说明**: - 在第一个测试用例中,一个可能的答案是 $[8, 2, 1]$,因为编号为 $8$ 的参与者在第 $1$ 天参与了彩票,但在第 $2$ 天和第 $3$ 天没有参与;编号为 $2$ 的参与者在第 $2$ 天参与了彩票,但在第 $3$ 天没有参与;编号为 $1$ 的参与者在第 $3$ 天参与了彩票。需要注意的是,这不是唯一的答案,例如,$[8, 9, 4]$ 也是正确的答案。 - 在第二个测试用例中,两个彩票参与者在两天都参与了,所以第 $1$ 天的任何可能的中奖者都必须在第 $2$ 天参与过彩票,这是不允许的。因此,没有正确的答案。 - 在第三个测试用例中,只有一位参与者在第 $2$、$3$、$4$ 天参与了彩票,而在第 $1$ 天只有一位参与者没有在第 $2, 3, 4$ 天参与彩票——编号为 $2$ 的参与者,这意味着 $[2, 1, 4, 3]$ 是这个测试用例的唯一正确答案。