Problem Description

There are $n$ students, numbered from $1$ to $n$. They have joined a total of $m$ clubs. For some strange reason, any two clubs share at most one common member.

Now the school wants to organize a contest and have these $n$ students stand in a circle. To prevent cheating, the principal wants any three consecutive people on the circle to not come from the same club.

The principal asks you to provide a valid circular arrangement of the students, or state that such an arrangement does not exist.

Input Format

The first line contains a positive integer $T$, which denotes the number of test cases.

For each test case:

The first line contains two non-negative integers $n, m$, representing the number of students and the number of clubs.

The next $m$ lines describe the clubs. In the $i$-th line, the first integer is $k_i$, the number of members in the $i$-th club, followed by $k_i$ distinct integers $a_{i,1}, a_{i,2}, \dots, a_{i, k_i}$, which are the student indices of the members in this club.

Output Format

For each test case, output one line:

If there exists a circular arrangement that satisfies the condition, output $n$ integers describing such an arrangement. If there are multiple valid arrangements, you may output any one of them.

If no such circular arrangement exists, output a single integer $-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 3 4 2 5
1 2 3 4 5 6 7
1 5 2 6 3 7 4 8
-1

见附件中的 contest2.in

见附件中的 contest2.ans

Hint

[Sample Explanation #1]

In the official judging, any circular arrangement that satisfies the condition is considered correct, no matter which student the arrangement starts from or which direction it goes.

[Sample Explanation #2]

In this sample, the first $110$ test cases satisfy $n \le 15$, and the last $35$ test cases satisfy $n \le 45$.

[Constraints]

For all test points, it is guaranteed that $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}$ are pairwise distinct, and the property stated in the problem holds (any two clubs share at most one common member).

The specific limits for each test point are shown in the table below:

You may use chk.cpp from the provided file (problem attachment) to check whether your output is valid. Compile it into an executable named chk before use.

• On Linux, run ./chk <input‐file> <output‐file> <answer‐file> to test.
• On Windows, run chk <input‐file> <output‐file> <answer‐file> to test.

Translated by ChatGPT 5