404045: GYM101401 I Data Structures Exam (B)

As predicted, a number of students were able to cheat during the last exam, and Doctor Sufyan wanted to avoid that in the future. He wanted to come up with a specific seating order beforehand that guarantees that no two friends will be able to cheat from each other, in case he had to use the meeting room again.

Given the number of students in his class N, which is equal to the number of seats around the table, and the pairs of friends that are likely to cheat from one another, determine whether or not it's possible to find a seating order that guarantees that no cheating incidents will occur.

The first line of input contains two space-separated integers N, M (3 ≤ N ≤ 10⁴) , the number of students (and seats) and the number of cheating pairs of friends, respectively.

Each of the following M lines contains two space-separated integers a b (1 ≤ a, b ≤ N) (a ≠ b), represent a pair of friends that are most likely to cheat.

It is guaranteed that each pair of students will appear at most once.

If it is impossible to find a seating order that guarantees that no cheating incidents will occur, print -1. Otherwise, print N distinct integers, on a single line, representing the seating order of the students around the table.

4 3
2 4
3 2
1 2

-1

10 7
1 4
7 3
2 9
9 6
5 10
5 9
8 2

1 4 2 9 6 10 5 8 3 7