P15869 【MX-X26-T5】「Cfz Round 7」anybody can finds love (expect you)

给定一张包含 $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 解释 对于第 $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）：无特殊限制。