F. One Touch Drawing
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Fengmi recently became obsessed with a small game called "One Touch Drawing". In this game, the map is an undirected graph containing $$$n$$$ vertices and $$$m$$$ edges. The graph may contain multiple edges and self-loops, and is not necessarily connected. The player needs to start from some vertex, walk along the edges of the graph, passing each edge exactly once, and finally stop at any vertex. After all edges have been passed exactly once, the game ends immediately.

This game adds a special "teleportation" mechanism: there are $$$k$$$ distinct pairs of "jump points". Each pair $$$(a, b)$$$ has the following property: whenever the player reaches vertex $$$a$$$ or vertex $$$b$$$ by traversing an edge, they are immediately teleported to the other vertex in the pair, and continue moving after the teleportation.

Special attention is required:

  • The starting point does not trigger teleportation (i.e., if the starting point is a jump point, no teleportation occurs when starting from that point);
  • The ending point also does not trigger teleportation (i.e., if the last step reaches a jump point, the game ends immediately without teleportation).

Fengmi wants to know whether there exists a path such that the player starts from some vertex, passes each edge exactly once, and strictly follows the above jumping rules. If it exists, output any such path (represented as a sequence of visited vertices), or report that no solution exists.

Input

The first line contains a positive integer $$$t$$$ ($$$1 \le t \le 5\times 10^4$$$) — the number of test cases.

For each test case:

The first line contains three positive integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m \le 10^6$$$, $$$1 \le k \le \lfloor \frac{n}{2} \rfloor$$$) — the number of vertices, the number of edges, and the number of jump point pairs, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), describing an undirected edge (multiple edges and self-loops may exist).

Each of the next $$$k$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$), indicating that $$$(a_i, b_i)$$$ is a pair of jump points. It is guaranteed that all $$$a, b$$$ are distinct (i.e., each vertex appears in at most one jump pair).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ does not exceed $$$10^6$$$.

Output

For each test case, if such a path exists: Output an integer $$$L$$$ on the first line — the number of visited vertices (including the start and end); On the second line, output $$$L$$$ integers separated by spaces, representing the sequence of vertex indices.

If it does not exist, output a single line containing $$$-1$$$.

Note: The path sequence must record the actual vertices reached (including vertices reached after teleportation). For example, going from vertex $$$1$$$ to $$$2$$$ (assuming $$$2$$$ is a jump point and teleports to $$$3$$$), then from $$$3$$$ to $$$4$$$, the output sequence would be $$$[1,2,3,4]$$$.

Example
Input
2
11 10 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
5 7
9 24 1
1 2
1 3
1 3
1 4
1 5
1 5
1 6
1 7
1 7
1 8
1 9
1 9
2 3
2 3
3 4
4 5
4 5
5 6
6 7
6 7
7 8
8 9
8 9
9 2
9 3
Output
13
1 2 3 4 5 7 6 5 7 8 9 10 11
30
5 6 7 8 9 3 4 5 4 1 9 3 2 9 3 2 1 9 3 
1 8 9 3 1 7 6 1 5 1 7
Note

For the first test case in the sample, $$$(5,7)$$$ is a jump point pair, as shown in the figure.

A valid path is: $$$1 \to 2 \to 3 \to 4 \to 5$$$ (teleports) $$$\to 7 \to 6 \to 5$$$ (teleports) $$$\to 7 \to 8 \to 9 \to 10 \to 11$$$.

For the second test case in the sample, as shown in the figure: