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.