题目描述

有 $N$ 名学生和 $N$ 份零食。学生和零食均分别编号为 $1,2,\cdots,N$。

每名学生都喜欢这 $N$ 份零食中的至少一份。更具体地，第 $i$（$1 \le i \le N$）名学生喜欢 $C_i$ 份零食，这些零食的编号分别为 $A_{i,1},A_{i,2},\cdots,A_{i,C_i}$。

起初，房间里恰好各放有一份这 $N$ 种零食。现要按照以下过程把零食分发给学生：

• 选择一个合适的顺序，每次让一名学生进入房间。
• 进入房间的学生会拿走房间中剩余的、自己喜欢的所有零食。如果房间中已经没有任何自己喜欢的零食，则什么也不拿。

请合理确定 $N$ 名学生进入房间的顺序，并判断是否能使每名学生都恰好拿走一份零食。若可以，请输出任意一种满足条件的顺序。

输入格式

第一行给出表示学生数和零食数的整数 $N$。

接下来的 $N$ 行给出 $N$ 名学生所喜欢零食的信息。其中第 $i$（$1 \le i \le N$）行依次给出以空格分隔的整数 $C_i$ 以及 $C_i$ 个整数 $A_{i,1},A_{i,2},\cdots,A_{i,C_i}$。

输出格式

如果不存在一种顺序能让所有学生都恰好拿走一份零食，则在第一行输出 -1。

如果学生按照 $P_1,P_2,\cdots,P_N$ 的编号顺序进入房间时，每名学生都能恰好拿走一份零食，则在第一行输出 $N$ 个以空格分隔的整数 $P_1,P_2,\cdots,P_N$。

如果存在多种可行输出，输出其中任意一种均视为正确。

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

提示

样例 1 解释

每名学生喜欢的零食如下：

• 第 $1$ 名学生喜欢第 $1$、第 $2$ 份零食。
• 第 $2$ 名学生喜欢第 $2$、第 $3$ 份零食。
• 第 $3$ 名学生喜欢第 $2$ 份零食。

若第 $3$、第 $1$、第 $2$ 名学生依次进入房间，则每名学生都恰好拿走一份零食。

• 起初，房间中第 $1$、第 $2$、第 $3$ 份零食各有一份。
• 第 $3$ 名学生进入房间后拿走第 $2$ 份零食。此后房间中剩下第 $1$、第 $3$ 份零食。
• 第 $1$ 名学生进入房间后拿走第 $1$ 份零食。此后房间中只剩下第 $3$ 份零食。
• 第 $2$ 名学生进入房间后拿走第 $3$ 份零食。

同理，即使第 $3$、第 $2$、第 $1$ 名学生依次进入房间，所有学生也都恰好拿走一份零食。

样例 2 解释

两名学生都喜欢全部两种零食，因此无论学生以何种顺序进入房间，最先进入的学生都会拿走所有零食。

限制条件

• 给出的所有数均为整数。
• $1 \le N \le 200\,000$
• 对于每个整数 $i$（$1 \le i \le N$），$1 \le C_i \le N$
• $C_1+C_2+\cdots+C_N \le 500\,000$
• 对于每个整数 $i$（$1 \le i \le N$）和整数 $j$（$1 \le j \le C_i$），$1 \le A_{i,j} \le N$
• 对于每个整数 $i$（$1 \le i \le N$），$C_i$ 个整数 $A_{i,1},A_{i,2},\cdots,A_{i,C_i}$ 两两不同。

子任务

1. （$6$ 分）对于每个整数 $i$（$1 \le i \le N$），$C_i=1$。
2. （$11$ 分）如果存在一种顺序能让所有学生都恰好拿走一份零食，那么学生按 $1,2,\cdots,N$ 的编号顺序进入房间也满足条件。
3. （$8$ 分）$N \le 5$。
4. （$12$ 分）$N \le 18$。
5. （$18$ 分）$N \le 300$。
6. （$20$ 分）$N \le 5\,000$。
7. （$25$ 分）没有额外限制。