700300 - 一笔画的路径
一笔画指从一点出发,每条路径仅经过一次,即可完成整个图形的绘制。
所以,达成一笔画的先决条件是图是联通的。
概念——奇点:和一个点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