Problem Statement

You are given a simple connected undirected graph with $N$ vertices numbered $1$ through $N$ and $M$ edges. The $i$-th edge connects vertices $a_i$ and $b_i$.

Determine whether there exists a cycle consisting of an odd number of vertices, and if one exists, find one such cycle.

Formally, determine whether there exists an integer sequence $(v_1,v_2,\ldots,v_K)$ satisfying all of the following conditions, and if one exists, find one such sequence.

• $K$ is an odd number at least $3$.
• $v_1,v_2,\ldots,v_K$ are all distinct.
• For every integer $i$ with $1\le i \le K$, there is an edge between vertices $v_i$ and $v_{i+1}$, where $v_{K+1} = v_1$.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \le T \le 2\times10^5$
• $1 \le N, M \le 2\times10^5$
• The sum of $N$ over all test cases is at most $2\times10^5$.
• The sum of $M$ over all test cases is at most $2\times10^5$.
• $1 \le a_i, b_i \le N$
• $a_i\ne b_i$
• The given graph is a simple connected undirected graph.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Each test case is given in the following format:

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

Output

For each test case, if there is no sequence satisfying the conditions, output -1. If one exists, output one such sequence in the following format:

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

If multiple sequences satisfy the conditions, any of them will be accepted.

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

In the first test case, the sequence $(2,1,3)$ satisfies the conditions: the edges $(2, 1), (1, 3), (3, 2)$ all exist. Outputs such as $v = (2, 3, 1)$ are also accepted.

In the second test case, there is no cycle with an odd number of vertices, so no sequence satisfies the conditions.

• Source: AtCoder ABC 472 E