You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC315E] Prerequisites

题面翻译

• 有 $N$ 本书，第 $i$ 本书有 $C_i$ 本前置读物 $P_{i,1},P_{i,2}\dots P_{i,c_i}$。
• 现在你想读第 $1$ 本书，问在读第 $1$ 本书之前至少还要读哪些书。
• 输出读它们的顺序，多解输出任意一个由于我们没有SPJ，请输出字典序最小的那个解。
• 保证有解，$1 \le N,\sum C_i \le 2\times 10^5$，其他数据在合理范围内。

题目描述

We have N books numbered 1 to N. Book i assumes that you have read Ci books, the j-th of which is book Pi,j: you must read all these Ci​ books before reading book �i. Here, you can read all the books in some order.

You are trying to read the minimum number of books required to read book 1. Print the numbers of the books you must read excluding book 1 in the order they should be read. Under this condition, the set of books to read is uniquely determined.

输入格式

输入格式如下。

$N$ $C_1$ $P_{1,1}$ $\ldots$ $P_{1,C_1}$ $C_2$ $P_{2,1}$ $\ldots$ $P_{2,C_2}$ $\vdots$ $C_N$ $P_{N,1}$ $\ldots$ $P_{N,C_N}$

输出格式

输出在可以读第1本书之前的一个读书序列，要求书本数量最少。如果有多个解，请输出字典序最小的那个解。

样例 #1

样例输入 #1

6
3 2 3 4
2 3 5
0
1 5
0
0

样例输出 #1

5 3 4 2

样例 #2

样例输入 #2

6
1 2
1 3
1 4
1 5
1 6
0

样例输出 #2

6 5 4 3 2

样例 #3

样例输入 #3

8
1 5
1 6
1 7
1 8
0
0
0
0

样例输出 #3

5

提示

数据范围

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ C_i\ <\ N$
• $\sum_{i=1}^{N}\ C_i\ \leq\ 2\ \times\ 10^5$
• $C_1\ \geq\ 1$
• $1\ \leq\ P_{i,j}\ \leq\ N$
• $1\ \leq\ j\ <\ k\ \leq\ C_i$ 且 $P_{i,j}\ \neq\ P_{i,k}$