Parallel Courses

You are given an integer n which indicates that there are 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 taken before course nextCourse_i (a prerequisite relationship).

In one semester, you can take any number of courses as long as all prerequisites for each course have been completed in a previous semester.

Return the minimum number of semesters needed to take all courses. If there is no way to take all courses (due to a cycle in prerequisites), return -1.

Examples

Example 1:

Input: n = 3, relations = [[1,3],[2,3]]

Output: 2

Explanation: In the first semester, courses 1 and 2 can be taken (no prerequisites). In the second semester, course 3 can be taken since both its prerequisites are complete.

Example 2:

Input: n = 3, relations = [[1,2],[2,3],[3,1]]

Output: -1

Explanation: There is a cycle (1 -> 2 -> 3 -> 1), so it is impossible to take all courses.

Example 3:

Input: n = 4, relations = [[1,2],[2,3],[3,4]]

Output: 4

Explanation: Each course depends on the previous one, so we must take them one at a time: semester 1 -> course 1, semester 2 -> course 2, semester 3 -> course 3, semester 4 -> course 4.

Constraints

• 1 <= n <= 5000
• 1 <= relations.length <= 5000
• relations[i].length == 2
• 1 <= prevCourse_i, nextCourse_i <= n
• prevCourse_i != nextCourse_i
• All pairs [prevCourse_i, nextCourse_i] are unique