Given an undirected connected graph $G=(V,E)$ with $n$ vertices and $m$ edges, which may contain multiple edges.

A sequence of edges $e_1, \dots, e_m$ is called "fishy" if and only if:

1. The multiset $\{e_i\}$ is identical to the edge set $E$;
2. For all $1 \le i < m$, the endpoint of $e_i$ is the same as the starting point of $e_{i+1}$;
3. For all $1 \le i \le m$, the starting point of $e_i$ is different from the endpoint of $e_{(i \bmod m)+1}$;
4. The starting point of $e_1$ is the same as the endpoint of $e_m$.

In other words, the sequence $e$ forms an Eulerian circuit, and the circuit does not contain any shape of $x \to y \to x$.

You need to construct a "fishy" sequence, or report that no such sequence exists.

For convenience, if a "fishy" sequence exists, you only need to output the vertices visited in the order of the circuit.

Input

The first line contains two integers $c$ and $t$, representing the subtask number and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case is then provided as follows:

• The first line contains two integers $n, m$.
• The next $m$ lines each contain two integers $x_i, y_i$, representing an edge connecting vertex $x_i$ and vertex $y_i$.

Output

For each test case:

• If no solution exists, output a single line containing $-1$.
• Otherwise, output a single line containing $m+1$ integers, representing the vertices visited in the order of the circuit.

Examples

Input 1

0 2
4 6
1 2
3 1
2 3
2 4
3 4
3 2
2 2
1 2
1 2

Output 1

2 3 1 2 3 4 2
-1

Note 1

For the first test case, $\{(1,2),(2,3),(3,4),(4,2),(2,3),(3,1)\}$ is also a "fishy" sequence, but $\{(2,4),(4,3),(3,2),(2,3),(3,1),(1,2)\}$ is not.

For the second test case, it is easy to prove that no "fishy" sequence exists.

Constraints

For all test cases:

• $1 \le t \le 10^5$;
• $1 \le n, m \le 10^6$, $\sum n \le 10^6$, $\sum m \le 10^6$;
• For all $1 \le i \le m$, $1 \le x_i, y_i \le n$ and $x_i \neq y_i$;
• The given undirected graph is connected.

This problem uses bundled testing.

• Subtask 1 (15 points): $\sum m \le 10$;
• Subtask 2 (18 points): $\sum m \le 20$;
• Subtask 3 (15 points): For all $1 \le u < v \le n$, there is at most $1$ edge connecting vertex $u$ and vertex $v$.
• Subtask 4 (24 points): For all $1 \le u < v \le n$, there are at most $2$ edges connecting vertex $u$ and vertex $v$.
• Subtask 5 (28 points): No special restrictions.