D - タスクの実行順序 解説 /

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

配点 : 400 点

問題文

高橋君は N 個のタスクをすべてこなす必要があります。それぞれのタスクには 1 から N までの番号が付けられており、各タスクはちょうど 1 回ずつ、1 つずつ順番に実行します。

タスクの間には前提条件があります。あるタスクを実行するには、それより先に別のタスクを完了していなければならない場合があります。この前提条件は M 個与えられ、各前提条件は「タスク A_i をタスク B_i より先に完了しなければならない」という形で表されます。

高橋君は、すべての前提条件を満たしながら N 個すべてのタスクを実行する順序を決めたいと考えています。そのような順序が存在する場合、実行するタスク番号を実行順に並べた列が辞書順最小となる実行順序を求めてください。前提条件に矛盾があり、すべてのタスクを実行することが不可能な場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M
  • N + M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • (A_i, B_i) の組はすべて異なる
  • 入力はすべて整数

入力

N M
A_1 B_1
A_2 B_2
:
A_M B_M
  • 1 行目には、タスクの数を表す整数 N と、前提条件の数を表す整数 M が、スペース区切りで与えられる。
  • 続く M 行では、前提条件が与えられる。
  • i 行目 (1 \leq i \leq M) では、タスク A_i をタスク B_i より先に完了しなければならないことを表す整数 A_i と B_i が、スペース区切りで与えられる。

出力

すべてのタスクを実行できる場合、辞書順最小の実行順序として N 個のタスク番号をスペース区切りで 1 行に出力してください。実行が不可能な場合は -1 を出力してください。

入力例 1

4 3
1 3
2 3
2 4

出力例 1

1 2 3 4

入力例 2

3 3
1 2
2 3
3 1

出力例 2

-1

入力例 3

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

出力例 3

1 2 3 4 5 6 7 8

入力例 4

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

出力例 4

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

入力例 5

1 0

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi needs to complete all N tasks. Each task is numbered from 1 to N, and each task is executed exactly once, one at a time, in some order.

There are prerequisite conditions between tasks. To execute a certain task, it may be necessary to have completed another task beforehand. There are M such prerequisite conditions given, each expressed in the form "Task A_i must be completed before Task B_i."

Takahashi wants to determine an order to execute all N tasks while satisfying all prerequisite conditions. If such an order exists, find the execution order such that the sequence of task numbers listed in execution order is lexicographically smallest. If the prerequisite conditions are contradictory and it is impossible to execute all tasks, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M
  • N + M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • All pairs (A_i, B_i) are distinct
  • All input values are integers

Input

N M
A_1 B_1
A_2 B_2
:
A_M B_M
  • The first line contains an integer N representing the number of tasks and an integer M representing the number of prerequisite conditions, separated by a space.
  • The following M lines give the prerequisite conditions.
  • The i-th line (1 \leq i \leq M) contains integers A_i and B_i separated by a space, indicating that Task A_i must be completed before Task B_i.

Output

If it is possible to execute all tasks, output the N task numbers in the lexicographically smallest execution order on a single line, separated by spaces. If execution is impossible, output -1.

Sample Input 1

4 3
1 3
2 3
2 4

Sample Output 1

1 2 3 4

Sample Input 2

3 3
1 2
2 3
3 1

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

1 2 3 4 5 6 7 8

Sample Input 4

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

Sample Output 4

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

Sample Input 5

1 0

Sample Output 5

1