왕국의 개발 계획

면접 대비

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

요약

프로젝트 n개와 선행 조건 쌍이 주어질 때 사전순으로 가장 작은 완료 순서를 구하고, 순환 의존이 있으면 IMPOSSIBLE을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 위상 정렬, 그래프, 힙
정답자: 아직 제출이 없습니다

문제

토프카리아 왕국은 인프라를 개선하기 위해 일련의 개발 사업을 계획하고 있다. 각 사업은 시작하기 전에 완료해야 하는 선행 조건을 가진다. 개발부는 모든 사업을 완료할 수 있는 실행 가능한 순서를 찾아 달라고 요청했다.

주어지는 것은 다음과 같다.

$n$ : 사업의 개수. 사업은 1번부터 $n$ 번까지 번호가 매겨져 있다.
$m$ : 선행 관계의 개수.
$m$ 개의 쌍 $(a, b)$ : 사업 $a$ 를 완료해야 사업 $b$ 를 시작할 수 있다는 뜻이다.

순환 의존성 때문에 모든 사업을 완료할 수 없으면 IMPOSSIBLE을 출력한다. 가능한 순서가 여러 개이면 사전순으로 가장 앞선 순서를 출력한다.

입력

첫 줄에 두 정수 $n$ 과 $m$ 이 주어진다. 이어지는 $m$ 개의 줄에는 각각 두 정수 $a$ 와 $b$ 가 주어진다. 이는 사업 $a$ 를 사업 $b$ 보다 먼저 완료해야 한다는 선행 관계를 뜻한다.

출력

완료할 수 없으면 IMPOSSIBLE을 출력한다. 완료할 수 있으면 유효한 완료 순서를 정수 $n$ 개로 한 줄에 출력한다. 유효한 순서가 여러 개이면 사전순으로 가장 앞선 순서를 출력한다. 두 순서가 처음으로 다른 위치에서 한쪽의 사업 번호가 더 작으면, 그 순서가 더 앞선다.

제한

$1 \le n \le 10^5$
$0 \le m \le 2 \times 10^5$
$a, b \in \{1, 2, \dots, n\}$
$a \ne b$
같은 쌍이 중복해서 주어지지 않는다.

예제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
```