普及⏱ 1000ms💾 256MB#P5148🏷️ 图论深度优先搜索

题目描述

市政处派一辆扫街车清扫城区街道:$n$ 个路口、$m$ 条街道(双向), 扫街车要沿街道行驶,每条街道恰好经过一次。 若存在这样的走法,则称存在欧拉路(回到起点则称欧拉回路)。

给定街道图,按上述经典算法(从最小奇度路口出发;若无奇点则从 $1$ 号路口出发, 每次走编号最小的可达路口)输出一条欧拉路/回路的路口序列。

输入格式

第一行两个整数 $n, m$; 以下 $m$ 行,每行两个整数,为一条街道连接的两个路口编号。

输出格式

一行,若干个整数:欧拉路/回路依次经过的路口编号,用空格分开。

数据范围

$$1 \le n \le 100$$
,图保证存在欧拉路或欧拉回路。

样例输入 #1
5 5
1 2
2 3
3 4
4 5
5 1
样例输出 #1
1 5 4 3 2 1
样例输入 #2
4 3
1 2
2 3
3 4
样例输出 #2
4 3 2 1