Lexicographically Smallest Final Ranking

There are (N) athletes numbered from (1) to (N) participating in a contest. During the contest, exactly (M) ranking changes occurred. In the (i)th ranking change, the two athletes (A_i) and (B_i) swapped positions. It is guaranteed that immediately before each swap the two athletes were adjacent in the ranking (i.e. there was no other athlete between them). However, the notes do not record which athlete moved up and which moved down.

A ranking table is a permutation (P = [P_1, P_2, \dots, P_N]) representing the final order (with (P_j) being the athlete in rank (j)). Your task is to decide whether there exists a final ranking table that does not contradict the recorded information. If such a ranking exists, output the lexicographically smallest one.

A permutation (a) is lexicographically smaller than a permutation (b) if and only if there exists an index (k) ((1 \le k \le N)) such that (a_1=b_1, a_2=b_2, \dots, a_{k-1}=b_{k-1}) and (a_k < b_k).

A valid final ranking (P) must be such that if one were to reverse simulate the (M) recorded swaps in reverse order (i.e. from swap (M) down to swap (1)), then at every step the two athletes that are to be swapped are consecutive. Formally, assume a candidate final ranking (P) and perform the following for (i=M,M-1,\dots,1): [ \text{Let } pos_{R}(x) \text{ denote the index (1-indexed) of athlete } x \text{ in the current ranking } R. ] For each (i) from (M) downto (1), if (|pos_{R}(A_i)-pos_{R}(B_i)| \neq 1) then (P) is not achievable; otherwise, swap the two athletes in (R) (this is the reverse of the recorded swap).

Your program should find the lexicographically smallest permutation (P) which passes this reverse simulation. If no such (P) exists, output -1.

inputFormat

The first line contains two integers (N) and (M) ((1 \le N \le 8), (0 \le M \le 10)). (Note: The constraints are small so that a brute‐force solution is acceptable.)

Then (M) lines follow. In the (i)th of these lines, two integers (A_i) and (B_i) are given ((1 \le A_i, B_i \le N,, A_i \neq B_i)). It is guaranteed that, immediately before each swap, the athletes (A_i) and (B_i) are adjacent in the ranking. No two swaps occur simultaneously.

If (M = 0), no further lines follow.

outputFormat

If there exists a final ranking that is consistent with the recorded information, output the lexicographically smallest permutation (P) of (1,2,\dots,N) (with values separated by a space). Otherwise, output -1.

sample

3 1
1 2

1 2 3