题目背景

如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。

欧拉回路有0个奇点，欧拉路有2个奇点（起点是一个奇点，终点是另一个奇点）。

奇点就是从这个点出发的线有奇数条，偶点就是从这个点出发的线有偶数条。

题目描述

有一个无向图，图中要么有0个奇点要么有2个奇点，如果存在欧拉回路请从第一个点（1号点）为起点开始遍历；如果有2个奇点，则从序号小的奇点开始遍历。在遍历的过程中，序号小的结点先遍历。

本题数据两结点之间可能有多条边，但保证存在欧拉路或者欧拉回路。

请输出一条字典序最小的欧拉路或者欧拉回路。

输入格式

第一行为整数n、m(1≤n≤100, 1≤m≤200)，表示图中点的个数（点编号为1~n）和边的个数；

每行有2个数，代表这两个点之间有一条边。

输出格式

满足条件的欧拉路或欧拉回路。

输入/输出样例

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

1 2 3 4 5 1

4 7
1 2
1 3
1 2
1 3
1 3
2 4
3 4

1 2 1 3 1 3 4 2

样例2解释

本输入样例存在重复边，如图所示：

说明/提示

时间1000ms，内存256MiB