Problem Description

You are given a connected undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges, where multiple edges may exist.

An edge sequence $e_1,\dots,e_m$ is called "鱼鱼" if and only if:

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

That is, the sequence $e$ forms an Eulerian circuit, and there is no pattern of the form $x \to y \to x$ in the circuit.

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

For convenience, when a "鱼鱼" sequence exists, you only need to output the vertices visited in order along the circuit.

Input Format

This problem has multiple test cases.

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

Then the test cases follow. For each test case:

• The first line contains two integers $n,m$.
• The next $m$ lines each contain two integers $x_i,y_i$, indicating that there is an edge connecting vertex $x_i$ and vertex $y_i$ in the graph.

Output Format

For each test case:

• If there is no solution, output one line containing a single integer $-1$.
• Otherwise, output one line containing $m+1$ integers, representing the vertices visited in order along the circuit.

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

2 3 1 2 3 4 2
-1

Hint

Sample 1 Explanation

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

For the $2$nd test case, it is easy to prove that no "鱼鱼" sequence exists.

Constraints

For all testdata:

• $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$, $x_i\neq y_i$;
• The given undirected graph is connected.

This problem uses bundled tests.

• 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 \lt v \le n$, there is at most $1$ edge connecting vertices $u$ and $v$.
• Subtask 4 (24 ponits): For all $1 \le u \lt v \le n$, there are at most $2$ edges connecting vertices $u$ and $v$.
• Subtask 5 (28 points): No special constraints.

Translated by ChatGPT 5