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

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

输入格式

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

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

输出格式

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

数据范围

$1 \le N \le 10^4$,
$1 \le M \le 5\*10^4$

输入样例：

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

输出样例：

1
2
3
4
2
1
4
3
2
4
1

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解