题目内容

小菊听说在一个神秘的城堡里藏着宝藏，她决定去寻宝。城堡由 $n$ 个房间组成，某些房间之间有通道相连。小菊从房间 $s$ 出发，想要到达藏有宝藏的房间 $t$。

给定房间数量 $n$、通道列表 edges、起点 $s$ 和终点 $t$，求小菊从起点到终点经过通道最短的路径长度（通道长度相同且长度为 $1$，例如：房间 $1 \rightarrow$ 房间 $2 \rightarrow$ 房间 $3$，经过 $2$ 条通道，长度 $=2$）。

如果起点终点相同，返回 $0$；如果房间无法到达，返回 $-1$。

输入描述

顶点数量 $n$：

• $1 \leq n \leq 10000$
• 顶点编号：从 $1$ 到 $n$（连续编号）
• 单顶点情况：$n = 1$ 时，起点终点相同，路径长度为 $0$

边数量和边参数 edges：

• 边数量 $m$：$0 \leq m \leq \min\left(\frac{n(n-1)}{2}, 100000\right)$
• 每条边 $[u, v]$：
  • $1 \leq u, v \leq n$（顶点编号合法）
  • $u$ 和 $v$ 可以相等（允许自环，但不影响路径长度）
  • 边是无向的：$(u, v)$ 表示房间 $u$ 和房间 $v$ 之间有一条双向通道
  • 允许重边：多条边连接同一对顶点（不影响最短路径）

起点和终点参数：

• 起点 $s$：$1 \leq s \leq n$
• 终点 $t$：$1 \leq t \leq n$

输出描述

返回从起点 $s$ 到终点 $t$ 的最短路径长度（经过的通道数）。若 $s = t$ 则返回 $0$；若不可达则返回 $-1$。

样例1

输入

4,[[1, 2], [2, 3], [3, 4], [1, 3]],1,4

输出

2

说明

• 路径 1（最短）：房间 $1 \rightarrow$ 房间 $3 \rightarrow$ 房间 $4$，经过 $2$ 条通道
• 路径 2（非最短）：房间 $1 \rightarrow$ 房间 $2 \rightarrow$ 房间 $3 \rightarrow$ 房间 $4$，经过 $3$ 条通道

样例2

输入

4,[[1, 2], [2, 1], [3, 4], [4, 3]],1,3

输出

-1

说明

• 房间 $1$ 和房间 $2$ 互相连通（含重边），房间 $3$ 和房间 $4$ 互相连通（含重边）
• 但两组之间没有通道，无法从房间 $1$ 到达房间 $3$，返回 $-1$

样例3

输入

5,[],1,1

输出

0

说明

• 没有任何通道，但起点和终点相同（都是房间 $1$），已在终点，路径长度为 $0$

样例4

输入

4,[[1, 1], [1, 2], [2, 3], [3, 4]],1,4

输出

3

说明

• 边 $[1,1]$ 为自环，不影响路径长度
• 最短路径：房间 $1 \rightarrow$ 房间 $2 \rightarrow$ 房间 $3 \rightarrow$ 房间 $4$，经过 $3$ 条通道，长度为 $3$

样例5

输入

6,[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [1, 6], [2, 5]],1,6

输出

1

说明

• 房间 $1$ 和房间 $6$ 之间有直接通道
• 最短路径：房间 $1 \rightarrow$ 房间 $6$，经过 $1$ 条通道，长度为 $1$
• 虽然也存在更长路径（如 $1 \rightarrow 2 \rightarrow 5 \rightarrow 6$，长度为 $3$），但最短路径长度为 $1$