Centre for Gifted Education - Hanoi university of Technology

Một đường đi Hamilton là một đường đi trong đồ thị vô hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Một Chu trình Hamilton là một đường đi Hamilton sau đi qua tất cả các đỉnh của đồ thị thì trở về đỉnh xuất phát.

Bài toán:

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm 1 chu trình Hamilton trên G

Input

Dòng 1: Chứa hai số n, m .

M dòng tiếp theo: Dòng thứ i có dạng hai số nguyên u, v. Trong đó u, v là chỉ số hai đỉnh đầu mút của cạnh thứ i.

Output

Gồm 1 dòng duy nhất là 1 dãy các số mô tả các đỉnh trên chu trình Hamilton

Example

Input:
5 6
1 2
1 3
2 4
3 5
4 1
5 2

Output:
1 3 5 2 4 1

Giới hạn:
1 <= n <= 30
1 <= m <=n(n-1)/2