Problem Description

There are $N$ students and $N$ snacks. Both students and snacks are numbered $1,2,\cdots,N$, respectively.

Each student likes at least one of these $N$ snacks. More specifically, student $i$ ($1 \le i \le N$) likes $C_i$ snacks, whose indices are $A_{i,1},A_{i,2},\cdots,A_{i,C_i}$.

At the beginning, there is exactly one copy of each of the $N$ types of snacks in the room. Now we distribute the snacks to the students using the following process:

• Choose a suitable order, and each time let one student enter the room.
• A student who enters the room will take away all remaining snacks in the room that they like. If there are no snacks left in the room that they like, they take nothing.

Please choose a suitable order for the $N$ students to enter the room, and determine whether it is possible to make every student take exactly one snack. If it is possible, output any order that satisfies the requirement.

Input Format

The first line contains an integer $N$, which represents the number of students and the number of snacks.

The next $N$ lines describe the snacks liked by the $N$ students. On line $i$ ($1 \le i \le N$), it gives the space-separated integer $C_i$ followed by $C_i$ integers $A_{i,1},A_{i,2},\cdots,A_{i,C_i}$.

Output Format

If there is no order that allows all students to take exactly one snack, output -1 on the first line.

If, when students enter the room in the order of indices $P_1,P_2,\cdots,P_N$, every student can take exactly one snack, then output $N$ space-separated integers $P_1,P_2,\cdots,P_N$ on the first line.

If there are multiple feasible outputs, any one of them will be accepted.

3
2 1 2
2 2 3
1 2

3 1 2

2
2 1 2
2 1 2

-1

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

1 2 3 4

Hint

Explanation of Sample 1

The snacks liked by each student are as follows:

• Student $1$ likes snack $1$ and snack $2$.
• Student $2$ likes snack $2$ and snack $3$.
• Student $3$ likes snack $2$.

If students $3$, $1$, and $2$ enter the room in this order, then each student will take exactly one snack.

• At the beginning, there is one copy each of snack $1$, snack $2$, and snack $3$ in the room.
• After student $3$ enters, they take snack $2$. After that, snacks $1$ and $3$ remain in the room.
• After student $1$ enters, they take snack $1$. After that, only snack $3$ remains in the room.
• After student $2$ enters, they take snack $3$.

Similarly, even if students $3$, $2$, and $1$ enter the room in this order, all students will still take exactly one snack.

Explanation of Sample 2

Both students like all $2$ types of snacks, so no matter in what order they enter the room, the first student to enter will take all snacks.

Constraints

• All given values are integers.
• $1 \le N \le 200\,000$
• For each integer $i$ ($1 \le i \le N$), $1 \le C_i \le N$
• $C_1+C_2+\cdots+C_N \le 500\,000$
• For each integer $i$ ($1 \le i \le N$) and integer $j$ ($1 \le j \le C_i$), $1 \le A_{i,j} \le N$
• For each integer $i$ ($1 \le i \le N$), the $C_i$ integers $A_{i,1},A_{i,2},\cdots,A_{i,C_i}$ are pairwise distinct.

Subtasks

1. ($6$ points) For each integer $i$ ($1 \le i \le N$), $C_i=1$.
2. ($11$ points) If there exists an order that allows all students to take exactly one snack, then the order $1,2,\cdots,N$ also satisfies the requirement.
3. ($8$ points) $N \le 5$.
4. ($12$ points) $N \le 18$.
5. ($18$ points) $N \le 300$.
6. ($20$ points) $N \le 5\,000$.
7. ($25$ points) No additional constraints.

Translated by ChatGPT 5