Kingdom’s Development Plan

시간 제한2초메모리 제한1024 MB

요약

n개의 프로젝트와 선행 관계 쌍이 주어질 때, 사전순으로 가장 작은 위상 정렬 순서를 출력하고 사이클이 있으면 IMPOSSIBLE을 출력한다.

난이도: 보통10점 중 6점
유형: 위상 정렬, 그래프, 힙, 그리디
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
5 5
1 2
2 3
2 4
2 5
3 4
```
예상 출력
```
1 2 3 4 5
```
예제 2
입력
```
5 4
1 2
2 3
3 1
5 4
```
예상 출력
```
IMPOSSIBLE
```