Three Sevens
Contest: Codeforces Round 860 (Div. 2)
Difficulty rating: 1000
Tags: brute force, data structures, greedy, implementation

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
8 2 1 
-1
2 1 4 3

Editorial:
Let's calculate the array $$$last$$$, where $$$last_X$$$ is the last day of the lottery in which the person $$$X$$$ participated. Then the only day when $$$X$$$ could be a winner is the day $$$last_X$$$. Then on the day of $$$i$$$, only the person with $$$last_X = i$$$ can be the winner. It is also clear that if there are several such participants for the day $$$i$$$, you can choose any of them as the winner, since these participants cannot be winners on any other days. In total, we need to go through all the days, if for some day there are no participants with $$$last$$$ equal to this day, then the answer is $$$-1$$$. Otherwise, we choose any participant with $$$last_X = i$$$ as the winner on the day of $$$i$$$.