结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

厂区里有 $n$ 个站点，编号 $1$ 到 $n$，站点之间铺了 $m$ 条双向通道，每条通道连接两个不同的站点。同两个站点之间可能铺有不止一条通道。

巡检员的日常规程是：每天从 $1$ 号站点出发，沿通道走遍全厂，每条通道恰好走一遍，走完回到 $1$ 号站点。收工时把途经的站点按先后顺序记成一行，就得到当天的巡检路线：它由 $m+1$ 个站点编号组成，第一个和最后一个都是 $1$。

程老师要安排的是这样一条路线。有的厂区排不出这样的路线，这时要如实报告没有路线。如果一个厂区能排出多条路线，程老师只留其中字典序最小的那一条：两条路线比较时，把途经站点的编号序列从头开始逐位对比，第一个不相同的位上编号小的那条更小（这种比法称为字典序比较）。

现在给出厂区的站点与通道清单，请你算出程老师要的那条路线。

输入格式

从文件 euler.in 中读入数据。

第一行两个整数 $n$ 和 $m$，分别表示站点数与通道数。

接下来 $m$ 行，每行两个整数 $u$ 和 $v$，表示一条连接 $u$ 号站点与 $v$ 号站点的双向通道。$u \neq v$。同两个站点之间的多条通道在输入中各占一行。

输出格式

输出到文件 euler.out 中。

一行。若这样的巡检路线不存在，输出 -1；否则输出 $m+1$ 个整数，为途经站点的编号序列，相邻两个整数之间用一个空格分隔，第一个与最后一个整数都是 $1$。

样例

3 3
1 2
2 3
1 3

1 2 3 1

解释

三条通道是 $1$–$2$、$2$–$3$、$1$–$3$。从 $1$ 号站点出发先走 $1$–$2$ 这条，到达 $2$ 号站点后剩下能走的只有 $2$–$3$，到 $3$ 号站点后只剩 $3$–$1$，走完正好回到 $1$ 号站点，三条通道各走过一遍，记下来是 $1\ 2\ 3\ 1$。若出发时先走 $1$–$3$，接下去依次是 $3$–$2$、$2$–$1$，记下来是 $1\ 3\ 2\ 1$。两条都符合规程，逐位对比时第二位是 $2$ 与 $3$，所以字典序最小的是 $1\ 2\ 3\ 1$。

2 1
1 2

-1

解释

厂区里只有一条通道，连接 $1$ 号与 $2$ 号站点。从 $1$ 号站点出发只能走这条通道到 $2$ 号站点，到了 $2$ 号站点以后没有别的通道可走，既去不了别处，也回不到 $1$ 号站点。因此排不出符合规程的路线，输出 -1。

数据范围

对于所有测试数据，保证：

• $2 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$；
• $1 \leq u, v \leq n$，$u \neq v$；
• 同两个站点之间可能有多条通道。

特殊性质 A：所有站点都被通道用到，每个站点恰好连着两条通道，并且从任意一个站点出发沿着通道走下去，会不重复地经过全部站点后回到出发的那个站点。

特殊性质 B：以 $1$ 号站点为一端的通道至少有 $4$ 条。