← 返回题目列表

Codeforces · 1693/C

C. 克什寻找 AmShZ

中文机器翻译题面 查看原题

AmShZ 已从伊朗前往意大利参加 Thom Yorke 音乐会。意大利有 $$$n$$$ 城市,索引从 $$$1$$$ 到 $$$n$$$,有 $$$m$$$ 定向道路,索引从 $$$1$$$ 到 $$$m$$$。最初,Keshi 位于城市 $$$1$$$,想要前往 AmShZ 在城市 $$$n$$$ 的家。由于Keshi不认识意大利地图,AmShZ帮助他尽快见到对方。

在每天开始时,AmShZ 可以向 Keshi 发送以下两条消息之一:

- AmShZ 将一条道路的索引作为阻塞道路发送到 Keshi。然后克什就会明白,他永远不应该走那条路,他将留在现在的城市。
- AmShZ 告诉 Keshi 移动。然后,克什会随机选择一个距离他当前城市可达的城市并移动到那里。 (如果有一条从城市 $$$A$$$ 到城市 $$$B$$$ 的外出道路尚未被封锁,则从城市 $$$A$$$ 可以到达城市 $$$B$$$。如果没有这样的城市,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$$$ 天后见面。

示例

输入 #1

2 1
1 2

输出 #1

1

输入 #2

4 4
1 2
1 4
2 4
1 4

输出 #2

2

输入 #3

5 7
1 2
2 3
3 5
1 4
4 3
4 5
3 1

输出 #3

4

注意

在第一个示例中,AmShZ 发送第二种类型的消息就足够了。

在第二个样本中,第一天,AmShZ 封锁了第一条路。因此,从城市 $$$1$$$ 唯一可到达的城市将是城市 $$$4$$$。因此第二天,AmShZ 可以告诉 Keshi 搬家,Keshi 就会到达 AmShZ 的家。

AmShZ 也可以告诉 Keshi 搬家两天。