集市排班

题目描述

森林集市连续举办了 $m$ 天。第 $i$ 天有 $n_i$ 位志愿者可供安排，编号为 $a_{i,1}, a_{i,2}, \ldots, a_{i,n_i}$。

已知规则如下：

• 每天必须从当天的候选人中选出 一名负责人；
• 被安排为第 $i$ 天负责人的志愿者，在接下来的第 $i+1$ 天到第 $m$ 天将 不再出现在候选名单中（他可能去执行其他任务）。

然而，原始的排班记录已经遗失。 请你帮助重新安排出一种可能的方案：为每一天选择一名负责人，使得所有规则均满足。 如果无法完成安排，则输出无解。

输入格式

输入包含多组测试用例。

• 第一行一个整数 $t$，表示测试用例数量（$1 \le t \le 50000$）。
• 对于每个测试用例：
  • 第一行一个整数 $m$（$1 \le m \le 50000$），表示天数；
  • 接下来对每个 $i = 1, 2, \ldots, m$：
    • 一行一个整数 $n_i$（$1 \le n_i \le 50000$），表示第 $i$ 天的候选人数；
    • 一行包含 $n_i$ 个互不相同的整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,n_i}$（$1 \le a_{i,j} \le 50000$），表示当天候选志愿者编号。

保证所有测试用例中 $\sum n_i \le 50000$。

输出格式

对于每个测试用例：

• 如果无解，输出一行 -1；
• 否则输出 $m$ 个整数 $p_1, p_2, \ldots, p_m$，其中 $p_i$ 表示第 $i$ 天选择的负责人编号。 若有多种方案，输出每天满足条件的最小编号。

输入样例

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

输出样例

8 2 1
-1
2 1 4 3

说明

• 在第一个测试用例中，方案 $[8, 2, 1]$ 合法：
  • 志愿者 $8$ 只在第 1 天出现；
  • 志愿者 $2$ 只在第 2 天出现；
  • 志愿者 $1$ 只在第 3 天出现。 例如 $[8, 9, 4]$ 也是正确答案。
• 在第二个测试用例中，两位志愿者在两天的名单中都出现，因此无论如何选择，第 1 天负责人的编号在第 2 天仍会出现，违反规则，因此无解。
• 在第三个测试用例中，第 2、3、4 天各只有 1 位候选人； 第 1 天中，只有编号 $2$ 未在之后的任何一天出现，因此唯一解为 $[2, 1, 4, 3]$。