← 返回题目列表

AtCoder · abc315_e

H. 先决条件

中文机器翻译题面 查看原题

分数: 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