← 返回题目列表

AtCoder · awc0028_d

D. 课程报名顺序

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

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