{"problem":{"name":"[WC/CTS2023] 比赛","description":{"content":"有 $n$ 名学生，标号从 $1$ 到 $n$，他们一共加入了 $m$ 个社团。由于一些奇怪的原因，**任意两个社团至多只包含一名公共成员**。 现在学校要组织一场比赛，想让这 $n$ 名学生围成一个圈。为了防止作弊，校长希望**圈上任意连续三个人不来自同一个社团**。 校长找到了你，希望你给他一组圆排列学生的方案，或指出这样的方案并不存在。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9074"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 名学生，标号从 $1$ 到 $n$，他们一共加入了 $m$ 个社团。由于一些奇怪的原因，**任意两个社团至多只包含一名公共成员**。\n\n现在学校要组织一场比赛，想让这 $n$ 名学生围成一个圈。为了防止作弊，校长希望**圈上任意连续三个人不来自同一个社团**。\n\n校长找到了你，希望你给他一组圆排列学生的方案，或指出这样的方案并不存在。\n\n## Input\n\n第一行包含一个正整数 $T$，表示数据组数。\n\n对于每组数据：\n\n第一行包含两个非负整数 $n, m$，分别表示学生的数量和社团的数量。\n\n接下来 $m$ 行，其中的第 $i$ 行的第一个整数为 $k_i$，表示第 $i$ 个社团的人数，紧随着 $k_i$ 个不重复的整数 $a_{i,1}, a_{i,2}, \\dots, a_{i, k_i}$，表示第 $i$ 个社团的成员的标号。\n\n## Output\n\n对于每组数据，输出一行：\n\n如果存在满足条件的圆排列，则该行包含 $n$ 个整数，表示一个满足条件的圆排列。**如果有多个满足条件的圆排列，输出任意一组均可**。\n\n如果不存在满足条件的圆排列，则该行仅包含一个整数 $-1$。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n在正式评测时，**任意一组满足条件的圆排列**都被视为正确，无论排列以谁开始，以哪个方向。\n\n**【样例解释 #2】**\n\n这个样例中前 $110$ 组数据满足 $n \\le 15$，后 $35$ 组数据满足 $n \\le 45$。\n\n**【数据范围】**\n\n对于所有的测试点，保证 $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$，$a_{i,1}, a_{i,2}, \\dots, a_{i,k_i}$ 互不相同，且满足题中所述性质（任意两个社团至多包含一名公共成员）。\n\n每个测试点的具体限制见下表：\n\n| 测试点编号 | $n$ | $m$ | 特殊性质 |\n| :-: | :-: | :-: | :-: |\n| $1 \\sim 2$ | $\\leq 9$ | 无 | 无 |\n| $3 \\sim 4$ | $\\leq 15$ | 无 | 无 |\n| $5 \\sim 6$ | $\\leq 45$ | 无 | 无 |\n| $7 \\sim 8$ | $\\leq 400$ | $= 1$ | 无 |\n| $9 \\sim 12$ | $\\leq 400$ | 无 | 保证 $a_{i,j+1} = a_{i,j} + 1$ |\n| $13 \\sim 16$ | $\\leq 400$ | 无 | 无 |\n| $17 \\sim 18$ | $\\leq 2000$ | $= 1$ | 无 |\n| $19 \\sim 21$ | $\\leq 2000$ | 无 | 保证 $a_{i,j+1} = a_{i,j} + 1$ |\n| $22 \\sim 25$ | $\\leq 2000$ | 无 | 无 |\n\n可以使用下发文件（题目附件）中的 `chk.cpp` 以检验你的输出的合法性，使用时先将其编译为可执行文件 `chk`。\n\n+ Linux 系统使用 `./chk <input‐file> <output‐file> <answer‐file>` 测试\n+ Windows 系统使用 `chk <input‐file> <output‐file> <answer‐file>` 测试。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9074","tags":["2023","Special Judge","O2优化","WC","CTSC/CTS"],"sample_group":[["4\n5 2\n3 1 2 3\n3 3 4 5\n7 7\n3 1 2 4\n3 2 3 5\n3 3 4 6\n3 4 5 7\n3 5 6 1\n3 6 7 2\n3 7 1 3\n8 2\n4 1 2 3 4\n4 5 6 7 8\n10 1\n10 1 2 3 4 5 6 7 8 9 10","1 3 4 2 5\n1 2 3 4 5 6 7\n1 5 2 6 3 7 4 8\n-1"],["见附件中的 contest2.in","见附件中的 contest2.ans"]],"created_at":"2026-03-03 11:09:25"}}