题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，每条边长度为 $1$ .

给定起点和终点，请求出起点到终点的最短距离，并输出一条从起点到终点的路径，如果有多条路径，任意一条路径都正确。

如果从起点出发无法到达终点，请输出 -1 .

输入格式

第 $1$ 行 , 两个整数 $n$ 和 $m$ , $n$ 表示点数， $m$ 表示边数；

接下来 $m$ 行，每行两个整数 $a$ 和 $b$ 表示 $a$ 与 $b$ 存在一条边。

最后一行两个整数 $s$ 和 $t$ , 表示起点和终点。

输出格式

第一行一个整数，表示起点到终点的最短距离。

第二行输出一条起点到终点的路径，格式见样例。

10 14
1 2
1 3
1 4
2 5
3 5
4 6
5 7
5 8
6 8
6 9
7 10
8 10
8 9
9 10
1 10

4
1 2 5 7 10

样例解释

数据代表的图如下：

从 1 到 10 最短距离是 4 ，其中一条路径是：1 -> 2 -> 5 -> 7 -> 10

数据规模与约定

$2 \le n \le 10^5, 2 \le m \le 3*n$

$subtask1$ : $2 \le n \le 10^3$

$subtask2$ : $2 \le n \le 10^5$

本题使用 spj :点击下载

类似题目

CSES - 1667 Message Route