Thứ tự tô-pô nhỏ nhất theo thứ tự từ điển

Mô tả bài toán

Khi một số công việc phụ thuộc lẫn nhau (làm xong việc u mới được làm việc v), ta cần xếp chúng thành một dãy mà mọi phụ thuộc đều được tôn trọng. Một dãy như vậy gọi là thứ tự tô-pô. Thường có nhiều dãy hợp lệ và người ta muốn dãy "đẹp" nhất theo thứ tự từ điển.

Yêu cầu

Cho đồ thị có hướng không chu trình (DAG) gồm n đỉnh đánh số 1..n và m cung. Cung u -> v nghĩa là u phải đứng trước v. Hãy in ra thứ tự tô-pô nhỏ nhất theo thứ tự từ điển: trong tất cả các dãy hợp lệ, chọn dãy sao cho phần tử đầu tiên nhỏ nhất có thể; nếu vẫn còn nhiều dãy, so tiếp phần tử thứ hai, rồi thứ ba, và cứ như vậy. Nói cách khác: ở mỗi bước, luôn chọn đỉnh nhỏ nhất trong số các đỉnh đã sẵn sàng (mọi đỉnh phải đứng trước nó đều đã được xếp).

Quy ước nộp bài

Nộp tệp solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Đúng n số trên một dòng, cách nhau một dấu cách, không in thêm chữ nào. Chỉ dùng thư viện chuẩn C++17.

Ràng buộc

• Đồ thị đảm bảo không có chu trình nên luôn tồn tại thứ tự tô-pô.
• Kết quả phải là dãy nhỏ nhất theo thứ tự từ điển, không phải một dãy hợp lệ bất kỳ.
• Mỗi bộ dữ liệu có thời gian chạy 1 giây.