• Tên file bài làm: TOPOSORT.cpp
• File dữ liệu vào: TOPOSORT.INP
• File kết quả: TOPOSORT.OUT
• Thời gian chạy: 1.0 giây

Đề bài

Cho một đồ thị có hướng gồm ~N~ đỉnh (được đánh số từ ~1~ đến ~N~) và ~M~ cung có hướng.

Một thứ tự tô-pô (Topological Ordering) của đồ thị là một hoán vị ~p = (p_1, p_2, \dots, p_N)~ của tập hợp ~\{1, 2, \dots, N\}~ sao cho với mọi cung có hướng từ đỉnh ~u~ đến đỉnh ~v~, đỉnh ~u~ luôn xuất hiện trước đỉnh ~v~ trong dãy hoán vị.

Yêu cầu: Hãy kiểm tra xem đồ thị đã cho có tồn tại thứ tự tô-pô hay không. Nếu có, hãy in ra một thứ tự tô-pô bất kỳ thỏa mãn. Nếu không tồn tại (đồ thị có chu trình), hãy in ra ~-1~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ (~1 \le N \le 10^5, 0 \le M \le 2 \times 10^5~) lần lượt là số đỉnh và số cung của đồ thị.
• ~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ô tả một cung có hướng từ đỉnh ~u~ đến đỉnh ~v~. Đồ thị có thể có nhiều cung giữa cùng một cặp đỉnh.

Kết quả

• Nếu đồ thị tồn tại thứ tự tô-pô, in ra trên một dòng duy nhất ~N~ số nguyên ~p_1, p_2, \dots, p_N~ cách nhau bởi dấu cách thể hiện thứ tự tô-pô tìm được.
• Nếu không tồn tại, in ra ~-1~.

Subtask

• Subtask 1 (30% số điểm): ~N \le 10, M \le 20~.
• Subtask 2 (30% số điểm): ~N \le 1000, M \le 2000~.
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm (~N \le 10^5, M \le 2 \times 10^5~).

Ví dụ

Sample Input 1

4 4
1 2
1 3
2 4
3 4

Sample Output 1

1 2 3 4

(Lưu ý: Dãy 1 3 2 4 cũng là một đáp án hợp lệ).

Sample Input 2

3 3
1 2
2 3
3 1

Sample Output 2

-1

Explanation

• Ở ví dụ 1: Đỉnh 1 phải đứng trước 2 và 3; đỉnh 2 và 3 phải đứng trước 4. Thứ tự 1 2 3 4 hoặc 1 3 2 4 đều thỏa mãn.
• Ở ví dụ 2: Tồn tại chu trình ~1 \to 2 \to 3 \to 1~ nên không thể sắp xếp tô-pô.