Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ 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 bấm vào xem bà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~ môn học được đánh số từ ~1~ đến ~n~ và ~m~ quan hệ tiên quyết: quan hệ ~(u, v)~ nghĩa là phải học xong môn ~u~ (ở một học kỳ trước đó) thì mới được học môn ~v~.

Trong mỗi học kỳ, bạn được học tối đa ~k~ môn, với điều kiện mọi môn tiên quyết của các môn đó đều đã được học ở các học kỳ trước. Hãy tìm số học kỳ ít nhất để học xong tất cả các môn. Dữ liệu đảm bảo luôn có cách học hết các môn (đồ thị tiên quyết không có chu trình).

Input

• Dòng đầu chứa số nguyên ~T~ ~(1 \le T \le 10)~ — số bộ test.
• Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên ~n, m, k~ ~\left(1 \le k \le n \le 15;\ 0 \le m \le \frac{n(n-1)}{2}\right)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1 \le u, v \le n;\ u \ne v)~ — môn ~u~ là tiên quyết của môn ~v~. Các cặp ~(u, v)~ đôi một khác nhau.

Output

Với mỗi bộ test, in ra trên một dòng số học kỳ ít nhất.

Subtask

• Subtask 1 (~20\%~ số điểm): ~k = n~.
• Subtask 2 (~80\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3
4 3 2
2 1
3 1
1 4
5 4 2
2 1
3 1
4 1
1 5
11 0 2

Sample Output 1

3
4
6

Giải thích

• Bộ test thứ nhất: học kỳ ~1~ học môn ~2, 3~; học kỳ ~2~ học môn ~1~; học kỳ ~3~ học môn ~4~.
• Bộ test thứ hai: học kỳ ~1~ học môn ~2, 3~; học kỳ ~2~ học môn ~4~; học kỳ ~3~ học môn ~1~; học kỳ ~4~ học môn ~5~.
• Bộ test thứ ba: không có quan hệ tiên quyết, mỗi học kỳ học ~2~ môn nên cần ~\lceil 11 / 2 \rceil = 6~ học kỳ.