F. Even Simple Path
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a simple undirected graph with $$$n$$$ vertices and $$$m$$$ edges.

A path is simple if it visits no vertex more than once. The length of a path is the number of edges in it.

Find a shortest simple path with even length from vertex $$$1$$$ to vertex $$$n$$$, or determine that no such path exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 1000$$$, $$$0\le m\le \frac{n(n-1)}2$$$) — the number of vertices and the number of edges in the graph.

Then $$$m$$$ lines follow, the $$$i$$$-th line containing two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\ne v_i$$$) — the two vertices that the $$$i$$$-th edge connects.

It is guaranteed that there are no self-loops or multiple edges in the graph.

It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$1000^3$$$.

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

Output

For each test case, if no such path exists, print $$$-1$$$.

Otherwise, print any shortest simple path of even length from vertex $$$1$$$ to vertex $$$n$$$:

  • On the first line, print its length $$$k$$$;
  • On the second line, print $$$k+1$$$ vertices $$$p_0,p_1,\ldots,p_k$$$ in order, where $$$p_0=1$$$ and $$$p_k=n$$$.

If there are multiple possible answers, you may print any of them.

Example
Input
5
2 0
3 2
1 2
2 3
4 3
1 2
2 3
3 4
5 4
1 5
1 2
2 5
3 4
6 7
1 6
1 2
2 3
3 4
4 6
2 5
4 5
Output
-1
2
1 2 3
-1
2
1 2 5
4
1 2 3 4 6
Note

In the first test case, there is no path from vertex $$$1$$$ to vertex $$$2$$$, so there is no answer.

In the second test case, the path $$$1 \to 2 \to 3$$$ has length $$$2$$$, and it is the shortest simple path with even length.

In the third test case, the only simple path from vertex $$$1$$$ to vertex $$$4$$$ has length $$$3$$$, which is not even, so there is no answer.

In the fourth test case, the path consisting only of the edge $$$1 \to 5$$$ has length $$$1$$$, which is odd and cannot be an answer. The path $$$1 \to 2 \to 5$$$ has length $$$2$$$.

In the fifth test case, the path $$$1 \to 2 \to 3 \to 4 \to 6$$$ has length $$$4$$$, while the path $$$1 \to 6$$$ has length $$$1$$$, which is not even.