Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Strange Graph
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 760Accepted: 154
Case Time Limit: 2000MSSpecial Judge

Description

Let us consider an undirected graph G = < V,E >. Let us denote by N(v) the set of vertices connected to vertex v (i.e. the set of neighbours of v). Recall that the number of vertices connected to v is called the degree of this vertex and is denoted by deg v.
We will call graph G strange if it is connected and for its every vertex v the following conditions are satisfied:
1. deg v >= 2 (i.e. there are at least two vertices connected to v)
2. If deg v = 2 then the two neighbours of v are not connected by an edge
3. If degv > 2 then there is u ∈ N(v), such that the following is true:
(a) deg u = 2
(b) Any two different vertices w1,w2 ∈ N(v) \ {u} are connected, i.e. (w1,w2) ∈ E.

You are given some strange graph G. Find hamiltonian cycle in it, i.e. find such cycle that it goes through every vertex of G exactly once.

Input

The first line of the input file contains two integer numbers N and M -- the number of vertices and edges in G respectively (3 <= N <= 10 000, M <= 100 000). 2M integer numbers follow -- each pair represents vertices connected by the corresponding edge (vertices are numbered from 1 to N). It is guaranteed that each edge occurs exactly once in the input file and that there are no loops (i.e. ends of each edge are distinct).

Output

If there is no hamiltonian cycle in G, print -1 on the first line of the output file. In the other case output N numbers -- the sequence of vertices of G as they appear in the hamiltonian cycle found (note that the last vertex must be connected to the first one). If there are several solutions, output any one.

Sample Input

4 4
1 2 2 3 3 4 4 1

Sample Output

1 2 3 4

Source

Northeastern Europe 2002, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator