P15869 [MX-X26-T5] "Cfz Round 7" anybody can finds love (expect you)

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.

**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.

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.

### 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