CF1798B.Three Sevens
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Lottery "Three Sevens" was held for m days. On day i , ni people with the numbers ai,1,…,ai,ni 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≤t≤50000 ). The description of the test cases follows.
The first line of each test case contains a single integer m ( 1≤m≤50000 ) — 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 ni ( 1≤ni≤50000 ) — the number of lottery participants on day i .
The second line of the block contains integers ai,1,…,ai,ni ( 1≤ai,j≤50000 ) — lottery participants on day i . It is guaranteed that all the numbers ai,1,…,ai,ni are pairwise distinct.
It is guaranteed that the sum of ni over all blocks of all test cases does not exceed 50000 .
输出格式
For each test case, if there is no solution, print a single integer −1 .
Otherwise, print m integers p1,p2,…,pm ( 1≤pi≤50000 ) — 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.