Lịch học ưu tiên nhỏ nhất

Bối cảnh và bài toán

Có n học phần với các quan hệ tiên quyết. Khi có nhiều học phần cùng đủ điều kiện học, nhà trường ưu tiên mã học phần nhỏ hơn.

Yêu cầu

In ra thứ tự học hợp lệ nhỏ nhất theo từ điển; nếu tồn tại chu trình phụ thuộc, in IMPOSSIBLE.

Input

Dòng đầu n, m; tiếp theo m cặp a, b nghĩa là a phải hoàn thành trước b.

Output

In thứ tự n mã học phần, hoặc "IMPOSSIBLE".

Ràng buộc

• 1 <= n <= 10^5
• 0 <= m <= 2*10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

5 3
1 2
3 1
4 5

Output

3 1 2 4 5

Giải thích. Trong mọi thời điểm, chọn học phần nhỏ nhất trong tập indegree 0 để đạt thứ tự hợp lệ nhỏ nhất từ điển.

Ví dụ 2

Input

3 3
1 2
2 3
3 1

Output

IMPOSSIBLE

Giải thích. Trong mọi thời điểm, chọn học phần nhỏ nhất trong tập indegree 0 để đạt thứ tự hợp lệ nhỏ nhất từ điển.

Gợi ý

Hãy bắt đầu bằng cách phân loại graph, mục tiêu truy vấn và constraints; sau đó đối chiếu với Decision Map của buổi học trước khi viết code.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Course Schedule. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.