Số học kỳ tối thiểu

Bối cảnh và bài toán

Mỗi học phần mất đúng một học kỳ. Trong cùng một học kỳ, có thể học đồng thời mọi học phần đã thỏa tất cả tiên quyết từ các học kỳ trước.

Yêu cầu

Tính số học kỳ tối thiểu để hoàn thành tất cả học phần; nếu phụ thuộc có chu trình, in -1.

Input

Dòng đầu n, m; tiếp theo m quan hệ a -> b.

Output

In số học kỳ tối thiểu hoặc -1.

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 2*10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

5 4
1 3
2 3
3 4
3 5

Output

3

Giải thích. Mỗi công việc chỉ bắt đầu sau tất cả prerequisite; học kỳ của nó bằng 1 cộng mức lớn nhất của predecessor.

Ví dụ 2

Input

3 3
1 2
2 3
3 1

Output

-1

Giải thích. Mỗi công việc chỉ bắt đầu sau tất cả prerequisite; học kỳ của nó bằng 1 cộng mức lớn nhất của predecessor.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.