← 返回 amazon 的题目列表Course Schedule Variant (Topological Sort)
类型:online_judge
Given n courses labeled 0..n-1 and prerequisite pairs prerequisites, where each pair [a, b] means you must take course b before course a.
Determine whether it is possible to finish all courses. If possible, output any valid course order; otherwise output IMPOSSIBLE.
Input
First line: two integers n and m.
Next m lines: two integers a b representing edge b -> a.
Output
If no valid ordering exists, print IMPOSSIBLE.
Otherwise print one line with n integers representing a valid ordering.
Constraints
1 <= n <= 2e5
0 <= m <= 2e5
0 <= a, b < n
Duplicate edges may exist.
Examples
See test cases in the Chinese version.
Example
Input
2 1
1 0
Output
0 1