说明

本题差SPJ，欢迎大家提供标准SPJ

题目描述

给定 $N$个点$M$条边的无向图，求一条路径，从节点 1 出发，最后回到节点 1，并且满足每条边恰好被沿着正、反两个方向分别经过一次。

若有多种方案，输出任意一种即可。

输入格式

第一行包含两个整数 $N$ 和$M$。

接下来 $M$行每行包含两个整数 $a$ 和$b$，表示点 $a$和点 $b$ 之间存在一条边。

输出格式

共 2$M$+1 行，每行包含一个整数，共同描述出了满足条件的一条路径。

样例

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

1
2
3
4
2
1
4
3
2
4
1

数据范围

$1≤N≤10^4, 1≤M≤5*10^4$

来源

• POJ2230
• USACO 2005 Jan.
• 算法竞赛进阶指南