Sắp xếp Tô-pô bằng thuật toán Kahn và phát hiện chu trình

Mục tiêu kiến thức

• Hiểu định nghĩa Thứ tự Tô-pô (Topological Sort) trên Đồ thị có hướng không chu trình (DAG - Directed Acyclic Graph).
• Cài đặt thuật toán Kahn (BFS dựa trên bán bậc vào in-degree).
• Phát hiện chu trình (Cycle Detection): Nếu sau khi duyệt số đỉnh được gán nhãn nhỏ hơn N, đồ thị có chu trình.
• Áp dụng Min-Heap (std::priority_queue với std::greater) để tìm thứ tự tô-pô có thứ tự từ điển nhỏ nhất (Lexicographically Smallest Topological Sort).

Mô tả bài toán

Hệ thống xử lý phân tán của AI Empire Academy cần lập lịch thực thi N tác vụ được đánh số từ 1 đến N (1 ≤ N ≤ 10⁵). Có M ràng buộc phụ thuộc (0 ≤ M ≤ 2 · 10⁵), mỗi ràng buộc dạng u → v có nghĩa là tác vụ u bắt buộc phải hoàn thành trước khi tác vụ v được phép bắt đầu.

Hãy tìm một thứ tự thực thi hợp lệ cho tất cả N tác vụ sao cho:

• Thỏa mãn toàn bộ M ràng buộc phụ thuộc.
• Nếu có nhiều thứ tự hợp lệ, hãy chọn thứ tự có thứ tự từ điển nhỏ nhất (tại mỗi bước, ưu tiên chọn tác vụ có số hiệu nhỏ nhất trong số các tác vụ đã sẵn sàng).
• Nếu tồn tại chu trình phụ thuộc (bế tắc luẩn quẩn, không thể hoàn thành tất cả các tác vụ), hãy in ra -1.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 10⁵.
• 0 ≤ M ≤ 2 · 10⁵.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.