Đăng đang trong đợt ôn thi học sinh giỏi cấp tỉnh nên có rất nhiều công việc cần hoàn thành. Các công việc được đánh số từ $1$ đến $n$. Có $m$ điều kiện, điều kiện thứ $i$ cho biết công việc ~x_i~ cần hoàn thành trước khi thực hiện công việc ~y_i~.
Độ quan trọng của một công việc được đánh giá bằng số lượng công việc khác bị ảnh hưởng khi không thực hiện công việc đó.
Bạn hãy giúp Đăng xác định công việc có độ quan trọng cao nhất để Đăng có thể tối ưu năng suất ôn tập của mình. Biết rằng, nếu có nhiều công việc có cùng độ quan trọng, Đăng sẽ ưu tiên công việc có số thứ tự thấp nhất. Ngoài ra, các điều kiện đảm bảo không có công việc nào phải hoàn thành trước chính nó.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ~(1 \le n, m \le 50\,000)~ - lần lượt là số lượng công việc và số lượng điều kiện.
- $m$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên ~x_i~ và ~y_i~ ~(1 \le x_i, y_i \le n)~ - mô tả điều kiện thứ $i$.
Kết quả
In ra một số nguyên duy nhất là số thứ tự của công việc có độ quan trọng cao nhất. Nếu có nhiều công việc có cùng độ quan trọng, hãy in ra công việc có số thứ tự thấp nhất.
Ràng buộc
- Subtask 1 ($60\%$ số điểm): $n, m \le 5\,000$;
- Subtask 2 ($40\%$ số điểm): không có ràng buộc gì thêm.
Ví dụ 1
Dữ liệu
3 2
1 2
2 3
Kết quả
1
Giải thích
- Công việc 1 cần hoàn thành trước 2 công việc 2 và 3, nên có độ quan trọng là $2$.
- Công việc 2 cần hoàn thành trước công việc 3, nên có độ quan trọng là $1$.
- Công việc 3 không làm ảnh hưởng công việc nào khác, nên có độ quan trọng là $0$.
- Do đó, công việc 1 có độ quan trọng cao nhất.
Ví dụ 2
Dữ liệu
6 8
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
Kết quả
1
Giải thích
- Độ quan trọng của các công việc theo thứ tự lần lượt là $4, 2, 3, 0, 1, 0$.
- Do đó, công việc 1 có độ quan trọng cao nhất.
Comments