anybody can finds love (expect you)

• 时间限制：$1.5$ 秒
• 空间限制：$512\text{ MB}$

题目描述

给定一张包含 $n$ 个点和 $m$ 条边的可能有重边的无向连通图 $G=(V,E)$。

定义一个由边构成的序列 $e_1,\dots,e_m$ 是「鱼鱼」的，当且仅当：

1. 可重集 $\{e_i\}$ 与边集 $E$ 相同；
2. 对于所有 $1 \le i \lt m$，$e_i$ 的终点与 $e_{i+1}$ 的起点相同；
3. 对于所有 $1 \le i \le m$，$e_i$ 的起点与 $e_{(i \bmod m)+1}$ 的终点不同；
4. $e_1$ 的起点与 $e_m$ 的终点相同。

即序列 $e$ 形成了一条欧拉回路，且回路中不存在 $x\to y\to x$ 的形状。

你需要构造一个「鱼鱼」的序列，或报告不存在「鱼鱼」的序列。

为了方便，当「鱼鱼」的序列存在时，你只需要按照回路的顺序给出经过的点即可。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 $c,t$，分别表示该测试点所属的子任务编号和测试数据组数。样例满足 $c=0$。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行包含两个整数 $n,m$。
• 接下来 $m$ 行，每行包含两个整数 $x_i,y_i$，表示图中存在一条连接结点 $x_i$ 和结点 $y_i$ 的边。

输出格式

对于每组测试数据：

• 如果无解，输出一行，包含一个整数 $-1$。
• 否则，输出一行，包含 $m+1$ 个整数，表示按照回路的顺序依次经过的点。

样例 1 输入

0 2
4 6
1 2
3 1
2 3
2 4
3 4
3 2
2 2
1 2
1 2

样例 1 输出

2 3 1 2 3 4 2
-1

样例 1 解释

对于第 $1$ 组测试数据，$\{(1,2),(2,3),(3,4),(4,2),(2,3),(3,1)\}$ 同样为「鱼鱼」的序列，但 $\{(2,4),(4,3),(3,2),(2,3),(3,1),(1,2)\}$ 不为「鱼鱼」的序列。

对于第 $2$ 组测试数据，容易证明不存在「鱼鱼」的序列。

数据范围

对于所有测试数据，均有：

• $1\le t\le 10^5$；
• $1\le n,m\le 10^6$，$\sum n\le 10^6$，$\sum m \le 10^6$；
• 对于所有 $1 \le i \le m$，均有 $1\le x_i,y_i\le n$，$x_i\neq y_i$；
• 给出的无向图连通。

本题采用捆绑测试。

• Subtask 1（15 points）：$\sum m\le 10$；
• Subtask 2（18 points）：$\sum m\le 20$；
• Subtask 3（15 points）：对于所有 $1 \le u \lt v \le n$，保证连接结点 $u$ 与结点 $v$ 的边不超过 $1$ 条。
• Subtask 4（24 ponits）：对于所有 $1 \le u \lt v \le n$，保证连接结点 $u$ 与结点 $v$ 的边不超过 $2$ 条。
• Subtask 5（28 points）：无特殊限制。