700300 - 一笔画的路径

Time Limit

1000 毫秒

Memory Limit

128 MB

通过次数

9

提交次数

12

一笔画指从一点出发,每条路径仅经过一次,即可完成整个图形的绘制。

所以,达成一笔画的先决条件是图是联通的。

概念——奇点:和一个点node连接的变数为奇数个,则称node为奇点。

条件——欧拉路径:图是联通的,且存在2个奇点。

条件——欧拉回路:图是联通的,且存在0个奇点。

欧拉路径:绘制时从任意一个奇点出发,沿着任意路径完成深搜即完成整个路径,但起点和终点不会重合。

欧拉回路:绘制时从任意一个点出发,沿着任意路径完成深搜即完成整个路径,且起点和终点会重合。

判断图的连通性:

广搜、深搜、并查集均可,三者效率均O(N)。

Input

第一行,有单个空格分隔的两个整数n,m,分别表示点的个数和边的个数。点编号为[1,n]。

接下来m行,每行两个整数x,y,表示编号为x,y的两点之间有一条边将两点连接起来。

对于100%的数据:

1\le m \le 100

2 \le n \le 100;

1\le x,y \le n

数据保证所给图一定是欧拉路径或欧拉回路,即能够一笔画完。

Output

输出欧拉路或欧拉回路全部路径中的字典序最小的一条。

Examples

Input

5 5
1 2
2 3
3 4
4 5
5 1

Output

1 2 3 4 5 1

Input

5 5
1 2
2 3
1 5
1 4
5 4

Output

1 4 5 1 2 3