32459번 - Kingdom’s Development Plan 다국어

문제

The Kingdom of Topcaria is planning a series of developmental projects to enhance its infrastructure. Each project has specific prerequisites that must be completed before the project can start. The Ministry of Development has asked you to help determine a feasible order in which all the projects can be completed.

You are given:

• $n,ドル the number of projects numbered from 1ドル$ to $n$.
• $m,ドル the number of prerequisite relationships between these projects.
• A list of $m$ pairs, where each pair $(a, b)$ indicates that project $a$ must be completed before project $b$ can start.

Your task is to determine an order in which all the projects can be completed. If it is impossible to complete all projects due to a cyclic dependency, output “IMPOSSIBLE”. If there are multiple valid orders, please output any the lexicographically smallest one.

입력

The first line contains two integers $n$ and $m$ — the number of projects and the number of prerequisite relationships. The next $m$ lines each contain two integers $a$ and $b$ — a prerequisite pair indicating that project $a$ must be completed before project $b$.

출력

If it is not possible, output “IMPOSSIBLE”. If it is possible to complete all projects, output a single line with $n$ integers — a valid order of project completions. If there are multiple possible orders, output the lexicographically smallest one. An order is lexicographically smaller than another order if at the first position where they differ, the project number on the first order is smaller than the number on the second order.

제한

• 1ドル ≤ n ≤ 10^5$
• 0ドル ≤ m ≤ 2 \times 10^5$
• $a, b \in \{1, 2,\dots ,n\}$
• $a \ne b$
• No duplicate pairs are given.

힌트