分数: 400 分
问题陈述
高桥正试图夺走一切 N 他大学的课程。
课程编号为 1 to N,每门课程只选一次。有些课程有先修课程,为了选修此类课程,必须事先完成所有先修课程。一门课程可能有多个先决条件。没有先决条件的课程可以从头开始学习。
有 M 给出的先决条件关系,每个关系的形式为:“为了学习课程 B_j,当然 A_j 必须先完成。”
高桥一次选一门课程。在每一步中,他尚未修读的课程中,其先决条件已全部完成(这些课程称为 可用课程),他选择数字最小的那个并拿走它。
输出高桥修读所有课程的顺序。
保证前提关系中不存在矛盾(即不存在循环),并且始终可以选修所有课程。此外,上述规则唯一地确定了注册的顺序。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq A_j \leq N (1 \leq j \leq M)
- 1 \leq B_j \leq N (1 \leq j \leq M)
- A_j \neq B_j (1 \leq j \leq M)
- If i \neq j,那么 (A_i, B_i) \neq (A_j, B_j) (同一先决关系不会多次给出)
- 先决关系中没有循环
- 所有输入值均为整数
输入
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
- 第一行包含一个整数 N 代表课程数量和一个整数 M 表示先决关系的数量,以空格分隔。
- 的 j- 以下各项 M 行 (1 \leq j \leq M) 包含整数 A_j 和 B_j 以空格分隔,表示当然 A_j 必须在上课前完成 B_j.
输出
在一行中输出高桥选修课程的顺序,并用空格分隔。即输出 N 整数按其获取顺序从左到右排列。
示例输入 1
4 3 1 2 3 4 2 4
示例输出 1
1 2 3 4
示例输入 2
5 3 2 1 3 1 5 4
示例输出 2
2 3 1 5 4
示例输入 3
10 8 1 3 2 3 3 5 4 5 5 10 6 7 8 9 7 10
示例输出 3
1 2 3 4 5 6 7 8 9 10
示例输入 4
15 12 15 14 14 13 13 12 12 11 1 5 2 5 5 6 3 7 8 9 9 10 4 10 6 11
示例输出 4
1 2 3 4 5 6 7 8 9 10 15 14 13 12 11
示例输入 5
1 0
示例输出 5
1