📖 Bài giảng & lời giải: đây là Bài tập 4 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

Có $n$ thành phố, đánh số $1..n$, và $m$ con đường hai chiều. Đoàn xe cần đi từ thành phố $1$ tới thành phố $n$ theo nhiều lộ trình, hai lộ trình bất kỳ không được đi chung một con đường (được phép đi qua chung thành phố). Có thể có nhiều con đường nối cùng hai thành phố; khi đó chúng được coi là những con đường khác nhau. Hỏi có thể chọn nhiều nhất bao nhiêu lộ trình?

Dữ liệu vào

• Dòng 1: hai số nguyên $n, m$ ($2 \le n \le 100$, $0 \le m \le 1000$).
• $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$): có một con đường hai chiều nối $u$ và $v$.

Kết quả

In ra một số nguyên là số lộ trình nhiều nhất (in $0$ nếu không đi được từ $1$ tới $n$).

Sample Input

4 5
1 2
1 3
2 3
2 4
3 4

Sample Output

2