CF1693C Keshi in Search of AmShZ

AmShZ 从伊朗前往意大利参加 Thom Yorke 的演唱会。意大利有 $n$ 个城市，编号从 $1$ 到 $n$，以及 $m$ 条有向道路，编号从 $1$ 到 $m$。最初，Keshi 位于城市 $1$，他想前往 AmShZ 的家——城市 $n$。由于 Keshi 不熟悉意大利的地图，AmShZ 会帮助他尽快见面。 每天开始时，AmShZ 可以向 Keshi 发送以下两种消息之一： - AmShZ 向 Keshi 发送一条道路的编号，表示该道路被封锁。此后，Keshi 会明白他永远不能再使用这条道路，并且当天会留在当前城市不动。 - AmShZ 告诉 Keshi 可以移动。此时，Keshi 会随机选择一个从当前城市出发且尚未被封锁的可达城市，并移动到那里（如果没有这样的城市，Keshi 会留在原地）。注意，AmShZ 始终知道 Keshi 的当前位置。 AmShZ 和 Keshi 想要找到一个最小的整数 $d$，使得他们可以确保在最多 $d$ 天后见面。请你帮助他们求出这个 $d$。

输入的第一行包含两个整数 $n$ 和 $m$，表示城市数量和道路数量 $(2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5)$。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $v_i$ 和 $u_i$ $(1 \le v_i, u_i \le n, v_i \neq u_i)$，表示一条从城市 $v_i$ 到城市 $u_i$ 的有向道路。 保证至少存在一条从城市 $1$ 到城市 $n$ 的路径。注意，任意一对城市之间可能存在多条道路，且方向可以不同。

输出一个最小的整数 $d$，使得 AmShZ 和 Keshi 可以确保在最多 $d$ 天后见面。

在第一个样例中，AmShZ 只需每天都发送第二种消息即可。 在第二个样例中，第一天 AmShZ 封锁第一条道路。这样，从城市 $1$ 唯一可达的城市就是城市 $4$。因此，第二天 AmShZ 可以让 Keshi 移动，Keshi 就能到达 AmShZ 的家。 当然，也可以选择连续两天都让 Keshi 移动。 由 ChatGPT 4.1 翻译