题目描述
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。
定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。
定理2：存在欧拉回路的条件：图是连通的，有0个奇点。
两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。
求欧拉路的算法很简单，使用深度优先遍历即可。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。
输入
第一行n，m，代表有n个点，m条边，
以下m行描述每条边连接的两点。
输出
欧拉路或欧拉回路
样例输入
5 5
1 2
2 3
3 4
4 5
5 1
样例输出
1 5 4 3 2 1
来源/分类