D - 科目の履修順序 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は大学で N 個の科目をすべて履修しようとしています。

科目には 1 から N までの番号が付けられており、各科目はちょうど 1 回ずつ履修します。一部の科目には前提科目（いわゆる「履修前提」）が設定されており、その科目を履修するには、前提科目をすべて先に履修し終えている必要があります。1 つの科目に対して前提科目が複数設定されていることもあります。前提科目が 1 つも設定されていない科目は、最初から履修可能です。

前提関係は M 個与えられ、各前提関係は「科目 B_j を履修するには、科目 A_j を先に履修し終えていなければならない」という形式です。

高橋君は科目を 1 つずつ履修していきます。各ステップにおいて、まだ履修していない科目のうち、前提科目をすべて履修済みであるもの（これを 履修可能な科目 と呼びます）の中から、番号が最も小さい科目を選んで履修します。

高橋君がすべての科目を履修するとき、科目を履修する順番を出力してください。

なお、前提関係に矛盾はなく（循環は存在せず）、必ずすべての科目を履修できることが保証されています。また、上記のルールにより履修順序は一意に定まります。

制約

  • 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)
  • 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
  • 1 行目には、科目の数を表す整数 N と、前提関係の数を表す整数 M が、スペース区切りで与えられる。
  • 続く M 行のうち j 番目の行 (1 \leq j \leq M) には、科目 B_j を履修する前に科目 A_j を履修し終えている必要があることを表す整数 A_j と B_j が、スペース区切りで与えられる。

出力

高橋君が科目を履修する順番を、スペース区切りで 1 行で出力せよ。すなわち、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

Score : 400 pts

Problem Statement

Takahashi is trying to take all N courses at his university.

The courses are numbered from 1 to N, and each course is taken exactly once. Some courses have prerequisite courses, and in order to take such a course, all of its prerequisite courses must have been completed beforehand. A single course may have multiple prerequisites. Courses with no prerequisites can be taken from the beginning.

There are M prerequisite relationships given, each in the form: "In order to take course B_j, course A_j must have been completed first."

Takahashi takes courses one at a time. At each step, among the courses he has not yet taken whose prerequisites have all been completed (these are called available courses), he selects the one with the smallest number and takes it.

Output the order in which Takahashi takes all the courses.

It is guaranteed that there are no contradictions in the prerequisite relationships (i.e., no cycles exist), and that it is always possible to take all courses. Furthermore, the above rule uniquely determines the order of enrollment.

Constraints

  • 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, then (A_i, B_i) \neq (A_j, B_j) (the same prerequisite relationship is not given more than once)
  • There are no cycles in the prerequisite relationships
  • All input values are integers

Input

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M
  • The first line contains an integer N representing the number of courses and an integer M representing the number of prerequisite relationships, separated by a space.
  • The j-th of the following M lines (1 \leq j \leq M) contains integers A_j and B_j separated by a space, indicating that course A_j must be completed before taking course B_j.

Output

Output the order in which Takahashi takes the courses on a single line, separated by spaces. That is, output N integers arranged from left to right in the order they are taken.

Sample Input 1

4 3
1 2
3 4
2 4

Sample Output 1

1 2 3 4

Sample Input 2

5 3
2 1
3 1
5 4

Sample Output 2

2 3 1 5 4

Sample Input 3

10 8
1 3
2 3
3 5
4 5
5 10
6 7
8 9
7 10

Sample Output 3

1 2 3 4 5 6 7 8 9 10

Sample Input 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

Sample Output 4

1 2 3 4 5 6 7 8 9 10 15 14 13 12 11

Sample Input 5

1 0

Sample Output 5

1