Sign up
Question
Course Semesters

A university offers N courses, numbered from 1 to N. There are M prerequisite rules. A rule (a, b) means course a must be completed strictly before course b.

In a single semester a student may take any number of courses at the same time, as long as every prerequisite of each chosen course has already been completed in an earlier semester.

Find the minimum number of semesters required to complete all N courses. If the prerequisites are contradictory (they form a cycle), completing every course is impossible.

Prerequisites are directed edges. This introduces directed graphs, topological ordering, and cycle detection through Kahn's algorithm, where each processing wave corresponds to one semester.

Input

The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of courses and the number of prerequisite rules.

Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, meaning course KaTeX can only parse string typed expression must be completed before course KaTeX can only parse string typed expression.

Output

Print the minimum number of semesters needed to finish all courses. If it is impossible, print KaTeX can only parse string typed expression.

Example
Example 1:
Input
4 4

1 2

1 3

2 4

3 4
Output
3
Explanation
Semester KaTeX can only parse string typed expression: take course KaTeX can only parse string typed expression. Semester KaTeX can only parse string typed expression: take courses KaTeX can only parse string typed expression and KaTeX can only parse string typed expression together. Semester KaTeX can only parse string typed expression: take course KaTeX can only parse string typed expression. Three semesters are needed.

Example 2:
Input
3 3

1 2

2 3

3 1
Output
-1
Explanation
The rules require KaTeX can only parse string typed expression before KaTeX can only parse string typed expression, KaTeX can only parse string typed expression before KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression before KaTeX can only parse string typed expression. This cycle can never be satisfied.

Example 3:
Input
4 0
Output
1
Explanation
No course has any prerequisite, so all four can be taken together in a single semester.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions