📖 Bài giảng & lời giải: đây là Bài tập 8 trong bài giảng Bài 43: Ghép cặp, luồng trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Nhà kho có $n$ trạm, đánh số $1..n$, nối bởi $m$ băng chuyền một chiều; băng chuyền $u \to v$ chở robot từ trạm $u$ tới trạm $v$. Hệ thống không có vòng tròn khép kín (đồ thị có hướng không chu trình – DAG). Mỗi robot xuất phát ở một trạm bất kỳ, đi theo các băng chuyền qua một số trạm (có thể không đi băng chuyền nào) rồi dừng ở một trạm bất kỳ. Mỗi trạm phải được đúng một robot đi qua (kể cả trạm xuất phát và trạm dừng). Hỏi cần ít nhất bao nhiêu robot?

Dữ liệu vào

• Dòng 1: hai số nguyên $n, m$ ($1 \le n \le 300$, $0 \le m \le 5000$).
• $m$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u, v$ ($1 \le u, v \le n$, $u \ne v$): băng chuyền từ $u$ tới $v$. Không có hai băng chuyền trùng nhau, đồ thị đảm bảo không có chu trình.

Kết quả

In ra một số nguyên là số robot ít nhất.

Sample Input

5 4
1 2
2 3
1 4
4 5

Sample Output

2

Note

Robot thứ nhất đi $1 \to 2 \to 3$, robot thứ hai đi $4 \to 5$. Một robot là không đủ vì từ trạm $1$ robot chỉ đi được theo một trong hai nhánh $1 \to 2 \to 3$ hoặc $1 \to 4 \to 5$.