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 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