BFS Shortest Path · GESP 7级 每日一题 Day01

题目描述

给定一个 $n$ 点 $m$ 条边的无向图（可能有自环或重边），求从 $1$ 号点到 $n$ 号点的最短路径所经过的边数。

如果 $1$ 与 $n$ 不连通，输出 -1。

第一行两个整数 $n, m$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一条无向边。

一行一个整数，表示 $1$ 到 $n$ 的最短路径边数，不连通输出 -1。

• $1 \le n \le 10^5$
• $0 \le m \le 2 \times 10^5$
• $1 \le u, v \le n$