Building the Perfect Array

You are helping a friend who is a computer scientist with a research project. The project requires finding an array that satisfies a certain set of constraints. Specifically, you are given p pairs of indices i and j, where i and j are indices of an array a of length n. Each pair (i, j) denotes a constraint that must be less than . Your task is to find an array a that satisfies all the given constraints.
The integers in the array a should be between 1 and inclusive.

Input

The first line of the input contains two integers n (2 ≤ n ≤ ) and p (1 ≤ p ≤ ), where n is the length of array a and p is the number of pairs. Each of the following p lines contains two space-separated integers i and j (1 ≤ i < j ≤ n), representing the pairs of indices that need to satisfy the constraint .

Output

If an array a can be found that satisfies all the given constraints, output a single line containing n space-separated integers, representing the array a. The integers in the array a should be between 1 and inclusive. If there are multiple possible solutions, output any one of them.
If it’s not possible to find such an array, the program should print Impossible.

Examples

Input
Output
4 2 1 2 4 1
2 3 4 1
5 5 1 2 2 3 3 4 5 4 2 5
2 4 6 8 5
3 3 1 2 2 3 3 1
Impossible

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue