Codeforces Round 800 (Div. 1) |
---|
Закончено |
AmShZ приехал в Италию из Ирана на концерт Тома Йорка. В Италии есть $$$n$$$ городов с номерами от $$$1$$$ до $$$n$$$ и $$$m$$$ ориентированных дорог с номерами от $$$1$$$ до $$$m$$$. Изначально Keshi находится в городе $$$1$$$ и хочет добраться к дому AmShZ в городе $$$n$$$. Поскольку Keshi не знает карту Италии, AmShZ помогает ему встретиться как можно скорее.
В начале каждого дня AmShZ может отправить 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)$$$ — количество городов и дорог соответственно.
В $$$i$$$-й строке из следующих $$$m$$$ строк содержится два целых числа $$$v_i$$$ и $$$u_i$$$ $$$(1 \le v_i , u_i \le n,v_i \neq u_i)$$$, обозначающих ориентированную дорогу, идущую из города $$$v_i$$$ в город $$$u_i$$$.
Гарантируется, что существует хотя бы один маршрут из города $$$1$$$ в город $$$n$$$. Обратите внимание, что между парой городов может быть более одной дороги в каждом направлении.
Выведите наименьшее возможное целое число $$$d$$$, при котором они могут быть уверены, что увидят друг друга через не более чем $$$d$$$ дней.
2 1 1 2
1
4 4 1 2 1 4 2 4 1 4
2
5 7 1 2 2 3 3 5 1 4 4 3 4 5 3 1
4
В первом примере достаточно, чтобы AmShZ отправил сообщение второго типа.
Во втором примере, в первый день, AmShZ блокирует первую дорогу. Поэтому единственным городом, до которого можно добраться из города $$$1$$$, будет город $$$4$$$. Следовательно, на второй день AmShZ может сказать Keshi двигаться, и Keshi прибудет в дом AmShZ.
AmShZ также может сказать Keshi двигаться в течение двух дней.
Название |
---|