← 返回 bytedance 的题目列表Course Schedule (Topological Sort / Cycle Detection)
类型：online_judge
Problem (Coding)
You are given n courses labeled 0..n-1 and a list of prerequisite relations prerequisites. Each relation is a pair (a, b), meaning to take course a you must first complete course b.
Return whether it is possible to finish all courses. Print true if possible, otherwise print false.
Input (stdin)
Line 1: integer n
Line 2: integer m (# of prerequisite pairs)
Next m lines: two integers a b
Output (stdout)
true or false
Constraints
1 <= n <= 2e5
0 <= m <= 2e5
0 <= a, b < n
Testcases
2
1
1 0
Output:
true
2
2
1 0
0 1
Output:
false
4
3
1 0
2 1
3 2
Output:
true
3
0
Output:
true
5
5
1 0
2 0
3 1
3 2
4 3
Output:
true
Example
Input
2
1
1 0
Output
true