#WC2023B. 比赛(民间数据)

比赛(民间数据)

题目描述

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

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

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

输入格式

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

对于每组数据:

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

接下来 mm 行,其中的第 i(1im)i (1 \le i \le m) 行的第一个整数为 kik_i,表示第 ii 个社团的人数,紧随着 kik_i 个不重复的整数 ai,1,ai,2,,ai,kia_{i,1}, a_{i,2},\dots, a_{i,k_i},表示第 ii 个社团的成员的标号。

输出格式

对于每组数据,输出一行:

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

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

样例 #1

样例输入 #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

提示

样例 11 解释

注意样例给出的答案仅为某一种可能的解,在正式评测时,任意一组满足条件的圆排列都被视为正确,无论排列以谁开始,以哪个方向。

样例 22

见题目附件中的 contest2.incontest2.ans,这个样例中前 110110 组数据满足 n15n \le 15,后 3535 组数据满足 n45n \le 45


子任务

对于所有的测试点,保证 $T \ge 1,n \ge 3,\sum n \le 2000,m \ge 0,3 \le k_i \le n,1 \le a_{i,j} \le n$,ai,1,ai,2,,ai,kia_{i,1}, a_{i,2}, \dots, a_{i,k_i} 互不相同,且满足题中所述性质(任意两个社团至多包含一名公共成员)。 每个测试点的具体限制见下表:

测试点编号 n n m m 特殊性质
12 1\sim 2 9 \le 9
34 3\sim 4 15 \le 15
56 5\sim 6 45 \le 45
78 7\sim 8 400 \le 400 =1 =1
912 9\sim 12 保证 ai,j+1=ai,j+1 a_{i,j+1}=a_{i,j}+1
1316 13\sim 16
1718 17\sim 18 2000 \le 2000 =1 =1
1921 19\sim 21 保证 ai,j+1=ai,j+1 a_{i,j+1}=a_{i,j}+1
2225 22\sim 25

提示

请点击题目右侧“文件”选项下载本题样例。

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

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