Optimal Dish Preparation Order

At the famous ATM Hotel, gourmet A is invited to taste a series of dishes. The hotel has prepared \(n\) dishes, numbered from 1 to \(n\) in order of their estimated quality (the highest quality dish is numbered 1). Due to the compatibility issues among dishes, there are \(m\) constraints of the form \((i, j)\), meaning that dish \(i\) must be prepared before dish \(j\).

The hotel wishes to determine an optimal preparation order such that gourmet A can taste the high quality dishes as early as possible. More precisely, the order should satisfy the following conditions:

1. Subject to all constraints, dish 1 is prepared as early as possible.
2. Subject to condition 1, dish 2 is prepared as early as possible.
3. Subject to conditions 1 and 2, dish 3 is prepared as early as possible.
4. And so on...

For example:

• Example 1: \(n=4\) and constraints \((3,1)\) and \((4,1)\). Although dish 1 has the highest quality, it cannot be made until dishes 3 and 4 are prepared. Among dishes 3 and 4, dish 3 (being of higher quality) should come first. Hence, the optimal order is: 3, 4, 1, 2.
• Example 2: \(n=5\) and constraints \((5,2)\) and \((4,3)\). Here, dish 1 can be made immediately. When considering dish 2, dish 5 must be prepared first; when considering dish 3, dish 4 must be prepared first. Thus, the optimal order is: 1, 5, 2, 4, 3.

If it is impossible to satisfy all constraints (i.e. if there is a cycle), output Impossible! (the first letter is uppercase and the rest are lowercase).

Note: The optimal order is defined hierarchically. That is, the position of dish 1 is minimized first; then, subject to that, the position of dish 2 is minimized; then dish 3; and so on.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of dishes and the number of constraints).

Each of the following \(m\) lines contains two integers \(i\) and \(j\), indicating that dish \(i\) must be prepared before dish \(j\).

\(1 \leq i,j \leq n\)

outputFormat

If a valid preparation order exists, output the order as \(n\) space-separated integers representing the dish numbers in the order they are prepared. If no valid order exists, output Impossible!

sample

4 2
3 1
4 1

3 4 1 2