CF2249F Even Simple Path

给定一个 $n$ 个点 $m$ 条边的无向简单图。 一条路径被称为简单路径，当且仅当它不会重复经过任意一个顶点。路径的长度是指其中的边数。 请你求出从顶点 $1$ 到顶点 $n$ 的一条最短的偶数长度简单路径，或判断是否不存在这样的路径。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每组测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 1000$，$0 \le m \le \frac{n(n-1)}2$），分别表示该图的点数和边数。 接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示该图中存在一条连接 $u_i$ 与 $v_i$ 的无向边。 保证没有自环或重边。 保证所有测试用例中 $n^3$ 之和不超过 $1000^3$。 保证所有测试用例中 $m$ 之和不超过 $10^6$。

对于每组测试用例，如果不存在满足条件的路径，输出 $-1$。 否则，输出一条 $1$ 到 $n$ 的最短偶数长度简单路径： - 第一行输出其长度 $k$； - 第二行输出 $k+1$ 个依次经过的顶点 $p_0, p_1, \ldots, p_k$，其中 $p_0 = 1$，$p_k = n$。 如有多种方案，输出任意一种即可。

在第一个测试用例中，$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$，不是偶数。 由 ChatGPT 5 翻译