分数: 425 点
问题陈述
我们有 N 书籍编号 1 to N.
书 i 假设您已阅读 C_i 书籍, j- 其中是书 P_{i,j}:你必须阅读所有这些 C_i 读书前的书 i.
在这里,您可以按某种顺序阅读所有书籍。
您正在尝试阅读阅读书籍所需的最少书籍数量 1.
打印您必须阅读的书籍数量(不包括书籍) 1 按照阅读顺序。在这种情况下,要读的书集是唯一确定的。
如果有多个满足条件的阅读指令,则可以打印任意一个。
约束
- 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
- P_{i,j} \neq P_{i,k} 为 1 \leq j < k \leq C_i.
- 可以阅读所有书籍。
输入
输入由标准输入按以下格式给出:
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
6 3 2 3 4 2 3 5 0 1 5 0 0
示例输出 1
5 3 4 2
读书 1,你必须读书 2,3,4;看书 2,你必须读书 3,5;看书 4,你必须看书 5。去读书 3,5,6,你不必阅读任何其他书籍。
例如,如果您读书 5,3,4,2 按此顺序,您可以阅读本书 1。这是正确答案,因为你永远无法读书 1 读过三本书或更少。另一个例子,看书 3,5,4,2 按此顺序还可以让您阅读本书 1 与 4 读过的书。
示例输入 2
6 1 2 1 3 1 4 1 5 1 6 0
示例输出 2
6 5 4 3 2
示例输入 3
8 1 5 1 6 1 7 1 8 0 0 0 0
示例输出 3
5