CF2249F.Even Simple Path

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.

给你一个包含 $n$ 个顶点和 $m$ 条边的简单无向图。

一条路径称为简单路径，如果它不重复访问任何顶点。路径的长度定义为该路径中边的数量。

请找出一条从顶点 $1$ 到顶点 $n$ 的最短简单路径，且其长度为偶数；若不存在这样的路径，则判定其不存在。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2\le n\le 1000$，$0\le m\le \frac{n(n-1)}2$）—— 分别表示图中的顶点数和边数。

接下来是 $m$ 行，其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i,v_i\le n$，$u_i\ne v_i$）—— 表示第 $i$ 条边所连接的两个顶点。

保证图中不存在自环或重边。

保证所有测试用例的 $n^3$ 之和不超过 $1000^3$。

保证所有测试用例的 $m$ 之和不超过 $10^6$。

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.

对于每个测试用例，若不存在这样的路径，则输出 $-1$。

否则，输出任意一条从顶点 $1$ 到顶点 $n$ 的最短简单路径，且该路径长度为偶数：

• 第一行输出其长度 $k$；
• 第二行按顺序输出 $k+1$ 个顶点 $p_0,p_1,\ldots,p_k$，其中 $p_0=1$ 且 $p_k=n$。

若存在多种可能的答案，输出任意一种即可。

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.

在第一个测试用例中，不存在从顶点 $1$ 到顶点 $2$ 的路径，因此无解。

在第二个测试用例中，路径 $1 \to 2 \to 3$ 的长度为 $2$，且它是长度为偶数的最短简单路径。

在第三个测试用例中，从顶点 $1$ 到顶点 $4$ 的唯一简单路径长度为 $3$，该长度为奇数，因此无解。

在第四个测试用例中，仅由边 $1 \to 5$ 构成的路径长度为 $1$，为奇数，不能作为答案；路径 $1 \to 2 \to 5$ 的长度为 $2$。

在第五个测试用例中，路径 $1 \to 2 \to 3 \to 4 \to 6$ 的长度为 $4$，而路径 $1 \to 6$ 的长度为 $1$，为奇数，不能作为答案。