Mid/Senior
Parallel Courses
You are given an integer n, representing n courses labeled from 1 to n. You are also given an array relations, where relations[i] = [prevCourse_i, nextCourse_i] means that course prevCourse_i must be completed before course nextCourse_i.
In one semester, you may take any number of courses as long as you have completed all prerequisites for each of those courses in previous semesters.
Return the minimum number of semesters needed to complete all courses. If it is impossible to complete all courses, return -1.
Example 1
Input
n = 3, relations = [[1,3],[2,3]]Output
2Courses 1 and 2 can be taken in the first semester, and course 3 can be taken in the second semester.
Example 2
Input
n = 3, relations = [[1,2],[2,3],[3,1]]Output
-1The prerequisites form a cycle, so it is impossible to complete all courses.
Constraints
- 1 <= n <= 5000
- 1 <= relations.length <= 5000
- relations[i].length == 2
- 1 <= prevCourse_i, nextCourse_i <= n
- prevCourse_i != nextCourse_i
- All the pairs [prevCourse_i, nextCourse_i] are unique.