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 搬家两天。