← 返回 bytedance 的题目列表Topological Sort on a Directed Graph
类型：online_judge
Given a directed graph with n nodes (labeled 0..n-1) and m directed edges, perform a topological sort:
If the graph contains a cycle, print IMPOSSIBLE.
Otherwise print any valid topological ordering (space-separated node labels).
Input
First line: two integers n m
Next m lines: two integers u v representing an edge u -> v
Output
If no topological ordering exists, output: IMPOSSIBLE
Otherwise output one line with a topological ordering of all n nodes.
Constraints
1 <= n <= 2e5
0 <= m <= 2e5
0 <= u, v < n
Sample Tests
Input:
4 3
0 1
1 2
0 3
Output:
0 1 3 2
Input:
3 3
0 1
1 2
2 0
Output:
IMPOSSIBLE
Input:
1 0
Output:
0
Input:
5 4
0 2
1 2
2 3
2 4
Output:
0 1 2 3 4
Input:
6 5
5 2
5 0
4 0
4 1
2 3
Output:
4 5 2 3 1 0
Example
Input
4 3
0 1
1 2
0 3
Output
0 1 3 2