1044. Parallel Courses — Minimum Semesters

There are n courses labeled 0..n-1 with prerequisite edges [a, b] meaning a must be taken before b. In each semester you may take any number of courses whose prerequisites are all satisfied. Return the minimum number of semesters to finish all courses, or -1 if impossible (a cycle exists). The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the minimum semesters, or -1.

Examples

Input: {"n":3,"edges":[[0,1],[0,2],[1,2]]}
Output: 3
Explanation: Take 0, then 1, then 2.

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: -1
Explanation: Cyclic dependency.

Input: {"n":1,"edges":[]}
Output: 1
Explanation: One semester.

Constraints

• 1<=n<=10^5
• directed prerequisites

Asked by