All problems

Parallel Courses

Medium · topological sort

A degree has n courses, numbered 1 to n. The degree is split into terms. In one term you may take as many courses as you like, all at the same time.

Some courses have requirements, given as a list relations of pairs [before, after]: course before must be finished in an earlier term than the term in which you take course after. The same pair may appear more than once.

Return the fewest terms needed to take every course. If it can never be done, return -1.

Examples

Example 1

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

Output: 3

Courses 1 and 2 go in term 1, course 3 in term 2 and course 4 in term 3.

Example 2

Input: n = 3, relations = []

Output: 1

Nothing is required, so all three courses fit in one term.

Example 3

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

Output: -1

Each course needs another one of the three to be finished first, so none of them can ever start.

Constraints