P9074 [WC/CTS2023] Contest

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.

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.

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$.

**[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: | Test Point ID | $n$ | $m$ | Special Property | | :-: | :-: | :-: | :-: | | $1 \sim 2$ | $\leq 9$ | None | None | | $3 \sim 4$ | $\leq 15$ | None | None | | $5 \sim 6$ | $\leq 45$ | None | None | | $7 \sim 8$ | $\leq 400$ | $= 1$ | None | | $9 \sim 12$ | $\leq 400$ | None | Guaranteed $a_{i,j+1} = a_{i,j} + 1$ | | $13 \sim 16$ | $\leq 400$ | None | None | | $17 \sim 18$ | $\leq 2000$ | $= 1$ | None | | $19 \sim 21$ | $\leq 2000$ | None | Guaranteed $a_{i,j+1} = a_{i,j} + 1$ | | $22 \sim 25$ | $\leq 2000$ | None | None | 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 ` to test. + On Windows, run `chk ` to test. Translated by ChatGPT 5