题目描述

给定一个 $N$ 个顶点、$M$ 条边的简单连通无向图，顶点编号为 $1$ 到 $N$。第 $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
case_1
case_2
...
case_T

其中每组测试数据的格式为：

N M
a_1 b_1
a_2 b_2
...
a_M b_M

输出格式

对每组测试数据：若不存在满足条件的序列，输出 -1；若存在，按下面的格式输出其中一个：

K
v_1 v_2 ... v_K

若满足条件的序列有多个，输出任意一个都算正确。

输入示例 1

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

输出示例 1

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

示例 1 说明

第一组中，序列 $(2,1,3)$ 满足条件：$(2,1)$、$(1,3)$、$(3,2)$ 都是图中的边。输出 $(2,3,1)$ 等也算正确。

第二组中不存在由奇数个顶点构成的环，所以输出 -1。

本题答案不唯一，评测采用 Special Judge：只要你输出的序列长度为奇数且不小于 $3$、顶点两两不同、相邻（含首尾）两点间都有边，就算正确；判定无解时也必须确实无解。

输入示例 2

3
2 1
1 2
4 4
1 2
2 3
3 4
1 4
5 6
1 2
2 3
3 4
4 5
1 5
2 5

输出示例 2

-1
-1
5
3 2 1 5 4

示例 2 说明

前两组都是二分图（一条边、一个四元环），没有奇环。

第三组在五元环的基础上多加了一条边 $(2,5)$，标准答案给出的是五元环 $(3,2,1,5,4)$。但图中同时还存在三元环 $(2,1,5)$，输出它同样正确——这组数据用来提醒：答案不必是最短的奇环，也不必与标准答案相同。

输入示例 3

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

输出示例 3

-1
7
4 3 2 1 7 6 5

示例 3 说明

第一组是一棵树，树上没有任何环，必然输出 -1。

第二组是一个七元环加一条弦 $(3,6)$。从顶点 $1$ 出发做 BFS，$4$ 与 $5$ 的深度相同（都是 $3$），沿 BFS 树把它们一路向上带到最近公共祖先 $1$，就拼出了长度为 $7$ 的奇环。这组数据用来检验沿 BFS 树向上找最近公共祖先这一步写得对不对：两个指针必须同步上移，中途任何一步走错都会拼出不合法的序列。

约束条件

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