题目描述

给定一张有 $N$ 个顶点（编号 $1$ 到 $N$）和 $M$ 条边的简单连通无向图。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

请判断是否存在一个由奇数个顶点构成的环，如果存在，找出一个这样的环。

形式化地说，请判断是否存在满足以下所有条件的整数序列 $(v_1,v_2,\ldots,v_K)$，如果存在，找出一个这样的序列。

• $K$ 是不小于 $3$ 的奇数。
• $v_1,v_2,\ldots,v_K$ 互不相同。
• 对于每个满足 $1\le i \le K$ 的整数 $i$，顶点 $v_i$ 与 $v_{i+1}$ 之间有边相连，其中 $v_{K+1} = v_1$。

给定 $T$ 组测试数据，请分别求解每组数据。

输入格式

输入以以下格式从标准输入给出：

• $T$
• $\mathrm{case}_1$
• $\mathrm{case}_2$
• $\vdots$
• $\mathrm{case}_T$

每组测试数据以以下格式给出：

• $N$ $M$
• $a_1$ $b_1$
• $a_2$ $b_2$
• $\vdots$
• $a_M$ $b_M$

输出格式

对于每组测试数据，如果不存在满足条件的序列，输出 -1。如果存在，按以下格式输出一个这样的序列：

• $K$
• $v_1$ $v_2$ $\ldots$ $v_K$

如果有多个序列满足条件，输出任意一个均可。

数据范围

• $1 \le T \le 2\times10^5$
• $1 \le N, M \le 2\times10^5$
• 所有测试数据中 $N$ 的总和不超过 $2\times10^5$。
• 所有测试数据中 $M$ 的总和不超过 $2\times10^5$。
• $1 \le a_i, b_i \le N$
• $a_i \ne b_i$
• 给定的图是简单连通无向图。
• 输入中的所有值均为整数。

4
3 3
1 2
2 3
1 3
7 7
1 2
2 3
3 4
1 4
4 5
5 6
6 7
5 5
1 2
2 3
3 4
4 5
1 5
9 10
1 2
2 3
3 4
4 5
1 5
6 7
7 8
8 9
6 9
1 6

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

在第一组测试数据中，序列 $(2,1,3)$ 满足条件：边 $(2, 1), (1, 3), (3, 2)$ 都存在。输出 $v = (2, 3, 1)$ 等也会被接受。

在第二组测试数据中，不存在由奇数个顶点构成的环，因此没有序列满足条件。

• 来源：AtCoder ABC 472 E

子任务设置

• 子任务 1（$30\%$）：$N, M \le 2000$，且各测试点中 $N$、$M$ 的总和同样不超过 $2000$。
• 子任务 2（$30\%$）：图是一棵树（$M = N - 1$，答案恒为 -1）。
• 子任务 3（$40\%$）：无特殊限制。