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.

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.