Kingdom's Development Plan

Interview

Time limit2sMemory limit1024 MB

Summary

Given n projects and prerequisite pairs, output the lexicographically smallest valid completion order, or IMPOSSIBLE if the dependencies contain a cycle.

Level: Easy3 of 10
Topics: Topological sort, Graph, Heap
Solved: No attempts yet

Problem

The Kingdom of Topcaria is planning a series of developmental projects to enhance its infrastructure. Each project has prerequisites that must be completed before it can start. The Ministry of Development wants you to find 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.
$m$ pairs $(a, b)$ , each meaning project $a$ must be completed before project $b$ can start.

If all projects cannot be completed because of a cyclic dependency, output IMPOSSIBLE. If several valid orders exist, output the lexicographically smallest one.

Input

The first line contains two integers $n$ and $m$ . Each of the next $m$ lines contains two integers $a$ and $b$ , a prerequisite pair meaning project $a$ must be completed before project $b$ .

Output

If it is impossible, output IMPOSSIBLE. Otherwise, output one line with $n$ integers, a valid completion order. If several orders are valid, output the lexicographically smallest one. An order is smaller than another if, at the first position where they differ, its project number is smaller.

Constraints

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

Examples2

Example 1
Input
```
5 5
1 2
2 3
2 4
2 5
3 4
```
Expected output
```
1 2 3 4 5
```
Example 2
Input
```
5 4
1 2
2 3
3 1
5 4
```
Expected output
```
IMPOSSIBLE
```