有 n 名学生,标号从 1 到 n,他们一共加入了 m 个社团。由于一些奇怪的原因,任意两个社团至多只包含一名公共成员。
现在学校要组织一场比赛,想让这 n 名学生围成一个圈。为了防止作弊,校长希望圈上任意连续三个人不来自同一个社团。
校长找到了你,希望你给他一组圆排列学生的方案,或指出这样的方案并不存在。
输入格式
第一行包含一个正整数 T,表示数据组数。
对于每组数据:
第一行包含两个非负整数 n,m,分别表示学生的数量和社团的数量。
接下来 m 行,其中的第 i(1≤i≤m) 行的第一个整数为 ki,表示第 i 个社团的人数,紧随着 ki 个不重复的整数 ai,1,ai,2,…,ai,ki,表示第 i 个社团的成员的标号。
输出格式
对于每组数据,输出一行:
如果存在满足条件的圆排列,则该行包含 n 个整数,表示一个满足条件的圆排列。如果有多个满足条件的圆排列,输出任意一组均可。
如果不存在满足条件的圆排列,则该行仅包含一个整数 −1。
样例一
input
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
output
1 3 4 2 5 1 2 3 4 5 6 7 1 5 2 6 3 7 4 8 -1
explanation
注意样例给出的答案仅为某一种可能的解,在正式评测时,任意一组满足条件的圆排列都被视为正确,无论排列以谁开始,以哪个方向。
样例二
见下发文件。这个样例中前 110 组数据满足 n≤15,后 35 组数据满足 n≤45。
子任务
对于所有的测试点,保证 T≥1,n≥3,∑n≤2000,m≥0,3≤ki≤n,1≤ai,j≤n,ai,1,ai,2,…,ai,ki 互不相同,且满足题中所述性质(任意两个社团至多包含一名公共成员)。
每个测试点的具体限制见下表:
子任务编号 | n | m | 特殊性质 | 分值 |
---|---|---|---|---|
1 | ≤9 | 无 | 无 | 6 |
2 | ≤15 | 6 | ||
3 | ≤45 | 6 | ||
4 | ≤400 | =1 | 10 | |
5 | 无 | 保证 ai,j+1=ai,j+1 | 15 | |
6 | 无 | 22 | ||
7 | ≤2000 | =1 | 6 | |
8 | 无 | 保证 ai,j+1=ai,j+1 | 11 | |
9 | 无 | 18 |
提示
可以使用下发文件中的 chk.cpp
以检验你的输出的合法性,使用时先将其编译为可执行文件 chk
。
- Linux 系统使用
./chk <input‐file> <output‐file> <answer‐file>
测试 - Windows 系统使用
chk <input‐file> <output‐file> <answer‐file>
测试。