Course Prerequisites Order

Course Prerequisites Order

There are n courses numbered 1..n and m prerequisite pairs (a, b) meaning course a must be completed ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​‌​‌‌​​‌‌​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​​​​‌‌​​​​​‌‌​​‌‌​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌​‌‌‌​​‌‌‌​​‌before course b. Determine a valid order to take all n courses.

If multiple valid orders exist, output the lexicographically smallest one (compare the sequences of course numbers as you would compare arrays: find the first position where they differ). If it is impossible to take all courses (a ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​‌​‌‌​​‌‌​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​​​​‌‌​​​​​‌‌​​‌‌​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌​‌‌‌​​‌‌‌​​‌cycle exists), output IMPOSSIBLE instead.

Input

Line 1: two integers n m (1 ≤ n ≤ 2·10^5, 0 ≤ m ≤ 2·10^5) Next m lines: two integers a b — course a before course b.

Output

Either n space-separated integers (the lexicographically smallest valid order), or the single word IMPOSSIBLE. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​‌​‌‌​​‌‌​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​​​​‌‌​​​​​‌‌​​‌‌​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌​‌‌‌​​‌‌‌​​‌

Example

Input:

4 3
1 2
1 3
3 4

Output:

1 2 3 4

Constraints

• 1 ≤ n ≤ 2·10^5, 0 ≤ m ≤ 2·10^5
• 1 ≤ a, b ≤ n ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​‌​‌‌​​‌‌​​​‌‌​​​​​​‌‌​‌​‌​​‌‌‌​​​​​‌‌​​​​​‌‌​​‌‌​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​​​​‌‌​​​​​​‌‌​​​​​​‌‌​‌​‌​​‌‌​‌‌‌​​‌‌‌​​‌

3 0

1 2 3

4 3
1 2
1 3
3 4

1 2 3 4