#2012. 「WC 2023 / CTS 2023」比赛

有 名学生，标号从 到 ，他们一共加入了 个社团。由于一些奇怪的原因，任意两个社团至多只包含一名公共成员。

现在学校要组织一场比赛，想让这 名学生围成一个圈。为了防止作弊，校长希望圈上任意连续三个人不来自同一个社团。

校长找到了你，希望你给他一组圆排列学生的方案，或指出这样的方案并不存在。

从文件 contest.in 中读入数据。

第一行包含一个正整数 ，表示数据组数。

对于每组数据：

第一行包含两个非负整数 ，分别表示学生的数量和社团的数量。

接下来 行，其中的第 行的第一个整数为 ，表示第 个社团的人数，紧随着 个不重复的整数 ，表示第 个社团的成员的标号。

输出到文件 contest.out 中。

对于每组数据，输出一行：

如果存在满足条件的圆排列，则该行包含 个整数，表示一个满足条件的圆排列。如果有多个满足条件的圆排列，输出任意一组均可。

如果不存在满足条件的圆排列，则该行仅包含一个整数 。

样例 1 输入

4
5 2
3 1 2 3
3 3 4 5
7 7
3 1 2 4
3 2 3 5
3 3 4 6
3 4 5 7
3 5 6 1
3 6 7 2
3 7 1 3
8 2
4 1 2 3 4
4 5 6 7 8
10 1
10 1 2 3 4 5 6 7 8 9 10

样例 1 输出

1 3 4 2 5
1 2 3 4 5 6 7
1 5 2 6 3 7 4 8
-1

样例 1 解释

注意样例给出的答案均为字典序最小的解，在正式评测时，任意一组满足条件的圆排列 都被视为正确，无论排列以谁开始，以哪个方向。

样例 2

见题目附件中的 contest2.in 和 contest2.ans，这个样例中前 组数据满足 ，后 组数据满足 。

对于所有的测试点，保证 ，，，，，， 互不相同，且满足题中所述性质（任意两个社团至多包含一名公共成员）。

每个测试点的具体限制见下表：

可以使用下发文件（题目附件）中的 chk.cpp 以检验你的输出的合法性，使用时先将其编译为可执行文件 chk。

• Linux 系统使用 ./chk <input‐file> <output‐file> <answer‐file> 测试
• Windows 系统使用 chk <input‐file> <output‐file> <answer‐file> 测试。