← 返回题目列表

Codeforces · 1798/B

B. 三七

中文机器翻译题面 查看原题

彩票“三七”已举办 $$$m$$$ 天。在$$$i$$$日,$$$n_i$$$号码为$$$a_{i, 1}, \ldots, a_{i, n_i}$$$的人参加了抽奖。

据了解,在$$$m$$$天的每一天中,从抽奖参与者中仅选出一名获奖者。 $$$i$$$日的抽奖者在$$$i+1$$$至$$$m$$$期间不得参加抽奖。

不幸的是,有关彩票中奖者的信息已丢失。您需要找到从 $$$1$$$ 到 $$$m$$$ 期间任何可能的彩票中奖者列表,或者确定不存在解决方案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 50\,000$$$) — 抽奖的天数。

接下来,对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$i$$$,后面跟着一个两行数据块。

每个块的第一行包含一个整数 $$$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]$$$是此测试用例的唯一正确答案。