404984: GYM101726 G Classroom Scheduling

The professors in Yekaterinburg University don't like to walk long distances. Each professor wishes that all classrooms he will give lectures in are in adjacent positions. In the beginning of each semester, the responsible for the Graduation Committee is charged with determining the classrooms the professors will give lectures. Each professor knows the groups he will teach, for example, students from the third semester of Mechanical Engineering, or students from the first semester of Computer Science, etc.

The students of each group stay in the same classroom for all lectures. The important thing is that all the classrooms each professor will lecture are adjacent. It is now always possible to satisfy the professors. If, for example, prof. A gives classes to groups X and Y, prof. B to groups Y and Z and prof. C to groups X and Z, it is clearly impossible to satisfy all of them. Your task is to help the responsible for the classroom schedule, determining if it is possible to satisfy all professors.

On the first line, a single integer T, the number of test cases.

The first line of each test case has two integers C and P, the number of classrooms (and groups) and the number of professors. The classrooms are numbered from 1 to C. The i-th of the next P lines describes the i-th professor. It consists of an integer K followed by K integers, denoting the groups the professor must teach, in increasing order.

Limits

• 1 ≤ T ≤ 10³
• 1 ≤ C ≤ 10³
• 1 ≤ P ≤ 10³
• The sum of C + P over all test cases does not exceed 2·10³
• 0 ≤ K ≤ C

For each test case, your program should print a permutation of the groups that satisfies all professors. If there's no such permutation, print -1. If more than one permutation is possible, print any of them.

2
5 4
3 2 4 5
2 2 5
2 1 5
2 1 3
3 3
2 1 2
2 2 3
2 1 3

4 2 5 1 3
-1