There are $n$ students, labeled from $1$ to $n$, who have joined $m$ clubs. For some strange reason, any two clubs share at most one common member.

The school is organizing a competition and wants to arrange these $n$ students in a circle. To prevent cheating, the principal requires that no three consecutive people in the circle belong to the same club.

The principal has asked you to provide a circular arrangement of the students or to indicate that no such arrangement exists.

Input

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

For each test case:

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

The next $m$ lines each describe a club. The $i$-th line ($1 \le i \le m$) starts with an integer $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}$, representing the labels of the members in the $i$-th club.

Output

For each test case, output one line:

If a valid circular arrangement exists, the line should contain $n$ integers representing the arrangement. If there are multiple valid circular arrangements, any one of them is acceptable.

If no such circular arrangement exists, the line should contain only the integer $-1$.

Examples

Input 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

Output 1

1 3 4 2 5
1 2 3 4 5 6 7
1 5 2 6 3 7 4 8
-1

Note

Note that the answers provided in the example are only one possible solution. In official testing, any circular arrangement that satisfies the conditions is considered correct, regardless of who the arrangement starts with or the direction of the sequence.

Input 2

See the provided files. In this example, the first $110$ test cases satisfy $n \le 15$, and the last $35$ test cases satisfy $n \le 45$.

Subtasks

For all test cases, 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$, and the members $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ are distinct. The condition that any two clubs share at most one common member is also guaranteed.

The specific constraints for each subtask are shown in the table below:

Note

You can use the chk.cpp file provided to verify the validity of your output. Compile it into an executable named chk before use.

• On Linux systems, use ./chk <input-file> <output-file> <answer-file> to test.
• On Windows systems, use chk <input-file> <output-file> <answer-file> to test.