U318869 一笔画问题

题目描述

如果一个图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。 根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行dfs,时间复杂度为 $O(m+n)$,$m$ 为边数,$n$ 是点数。 ---------------------------------------------------------------------------------------------------------------- PS:如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)。 如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit) 具有欧拉回路的图称为欧拉图(简称E图)。 欧拉由此提出 了著名的欧拉定理。 1)欧拉路:通过图中所有边的路径。 2)欧拉回路:闭合的欧拉路。 3)欧拉图:包含欧拉回路的图。

输入格式

第一行 $n$,$m$,有 $n$ 个点,$m$ 条边,以下 $m$ 行描述每条边连接的两点。

输出格式

欧拉路或欧拉回路,输出一条路径即可。(字典序最小)

说明/提示

【数据范围】 对于 $100%$ 的数据:$1 < n \lt 100$,$1 < m \lt 2000$。