有 $n$ 名学生，标号从 $1$ 到 $n$，他们一共加入了 $m$ 个社团。由于一些奇怪的原因，任意两个社团至多只包含一名公共成员。
现在学校要组织一场比赛，想让这 $n$ 名学生围成一个圈。为了防止作弊，校长希望圈上任意连续三个人不来自同一个社团。
校长找到了你，希望你给他一组圆排列学生的方案，或指出这样的方案并不存在。
输入格式
第一行包含一个正整数 $T$，表示数据组数。
对于每组数据：
第一行包含两个非负整数 $n, m$，分别表示学生的数量和社团的数量。
接下来 $m$ 行，其中的第 $i (1 \le i \le m)$ 行的第一个整数为 $k_i$，表示第 $i$ 个社团的人数，紧随着 $k_i$ 个不重复的整数 $a_{i,1}, a_{i,2},\dots, a_{i,k_i}$，表示第 $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 \le 15$，后 $35$ 组数据满足 $n \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$，$a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ 互不相同，且满足题中所述性质（任意两个社团至多包含一名公共成员）。
每个测试点的具体限制见下表：
| 子任务编号 | $n$ | $m$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $\leq 9$ | 无 | 无 | $6$ |
| $2$ | $\leq 15$ | $6$ | ||
| $3$ | $\leq 45$ | $6$ | ||
| $4$ | $\leq 400$ | $=1$ | $10$ | |
| $5$ | 无 | 保证 $a_{i,j+1} = a_{i,j} + 1$ | $15$ | |
| $6$ | 无 | $22$ | ||
| $7$ | $\leq 2\,000$ | $=1$ | $6$ | |
| $8$ | 无 | 保证 $a_{i,j+1} = a_{i,j} + 1$ | $11$ | |
| $9$ | 无 | $18$ |
提示
可以使用下发文件中的 chk.cpp 以检验你的输出的合法性，使用时先将其编译为可执行文件 chk。
- Linux 系统使用
./chk <input‐file> <output‐file> <answer‐file>测试 - Windows 系统使用
chk <input‐file> <output‐file> <answer‐file>测试。