Migrated from Lutece 3154 利萨斯陷落

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

时间来到 LP0002 年，利萨斯王城突然被赫尔曼士兵入侵，忍者加奈美找到兰斯，希望兰斯能够出手拯救利萨斯王国。

一番折腾后，兰斯终于答应帮助利萨斯王国击退赫尔曼和魔人，于是让希露（也就是你）规划一条完美路径。

具体来说，要求如下：

被赫尔曼和魔人占领的有 $n$ 个城市，有 $m$ 条双向道路连接这些城市，没有一条道路是自己连向自己的，没有一条道路连接的城市完全相同。

$n$ 个城市和 $m$ 条道路都有赫尔曼士兵或魔人驻守，$n$ 个城市编号为 $1 \sim n$，现在假定兰斯一经过某个城市或者道路就能通过某种方式扫荡该处的的敌人。

兰斯能让忍者加奈美首先带到任意一个城市作为出发点，也就是说，希露（也就是你）可以指定任意一个点作为出发点，并且从此出发，找到一条扫荡路径——满足在经过所有城市的基础上（出发点默认在开始时就已经经过），每条道路都会经过一次且仅有一次。如果能找到这样路径，请输出途中经过的城市编号；如果不能找到，则输出 -1。

因为兰斯大爷有强迫症，所以如果有多条满足条件的路径，请你给出字典序最小的路径。

Input

第一行两个正整数，分别代表 $n$ 和 $m$。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$，代表一条双向道路连接了编号为 $u$ 和 $v$ 的城市。

Output

如果不能找到这样的道路，则输出 $-1$ 即可。

如果能找到，请输出一行，该行应有 $m + 1$ 个正整数，代表你规划的路径所经过的城市编号（如果有多条，请输出字典序最小的一条）。

Samples

3 3
1 2
2 3
1 3

1 2 3 1

4 3
1 2
2 3
1 3

-1

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

1 2 3 4 2 5 3 1

Constraints

$1 \le n \le 5 \times 10^5$

$1 \le m \le \min(\dfrac{n \times (n - 1)}{2}, 5 \times 10^5)$

$1 \le u, v \le n$

Note

希望你能够规划一条完美路径，否则你会受到兰斯大人超级兵器的惩罚。

神中神：

我が栄光

ロイヤルチェイサー

Resources

2024 UESTC ICPC Training for Graph