题目描述

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

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

输入格式

第一行包含两个整数$\red {N}$和$\red {M}$。

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

输出格式

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

样例

输入样例

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

输出样例

1
2
3
4
2
1
4
3
2
4
1

提示

$\red {1≤N≤10^4}$,

$\red {1≤M≤5\times 10^4}$