烽塔最远回声

题目描述

边境线上一共有 $n$ 座烽塔，编号为 $1$ 到 $n$。一些烽塔之间修有双向石道，因此消息可以沿着石道一站一站地传递。

传令官从烽塔 $s$ 发出一封急报。每经过一条石道，急报就会多花费 $1$ 个时刻才能到达下一座烽塔。

现在他想知道： 如果所有能够收到急报的烽塔都尽快传递，那么最晚会在第几个时刻传到最远的一座烽塔？

如果存在某些烽塔从 $s$ 出发永远无法到达，请输出 $-1$。

输入格式

第一行包含三个整数 $n, m, s$。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示烽塔 $u$ 和烽塔 $v$ 之间有一条双向石道。

输出格式

输出一个整数，表示最远可达烽塔收到急报的最晚时刻；如果存在不可达烽塔，则输出 $-1$。

输入输出样例 #1

输入 #1

5 4 1
1 2
2 3
3 4
4 5

输出 #1

4

输入输出样例 #2

输入 #2

6 3 1
1 2
2 3
5 6

输出 #2

-1

数据范围

对于 $50\%$ 的数据，$1 \le n \le 1000$，$0 \le m \le 5000$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le m \le 2 \times 10^5$，$1 \le s, u, v \le n$，$u \ne v$。

建议

一刷、二刷