Course Schedule II

Medium

graphtopological-sortheap

Same setup as Course Schedule: n courses and prerequisite pairs a b (take b before a). Return a valid order to take all courses; among valid orders return the lexicographically smallest. If impossible, print -1.

Input

Line 1: n m
Next m lines: a b

Output: the order, space-separated — or -1.

Example 1

Input:

2 1
1 0

Output:

0 1

Example 2

Input:

Output:

0 1 2 3

Example 3

Input:

2 2
1 0
0 1

Output:

-1

Constraints

1 ≤ n ≤ 2000
0 ≤ m ≤ 5000

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Course Schedule II

Medium

graphtopological-sortheap

Input

Line 1: n m
Next m lines: a b

Output: the order, space-separated — or -1.

Example 1

Input:

2 1
1 0

Output:

0 1

Example 2

Input:

Output:

0 1 2 3

Example 3

Input:

2 2
1 0
0 1

Output:

-1

Constraints

1 ≤ n ≤ 2000
0 ≤ m ≤ 5000

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.