C. Keshi ищет AmShZ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

AmShZ приехал в Италию из Ирана на концерт Тома Йорка. В Италии есть $$$n$$$ городов с номерами от $$$1$$$ до $$$n$$$ и $$$m$$$ ориентированных дорог с номерами от $$$1$$$ до $$$m$$$. Изначально Keshi находится в городе $$$1$$$ и хочет добраться к дому AmShZ в городе $$$n$$$. Поскольку Keshi не знает карту Италии, AmShZ помогает ему встретиться как можно скорее.

В начале каждого дня AmShZ может отправить Keshi одно из следующих двух сообщений:

  • AmShZ отправляет Keshi номер одной дороги, обозначая её как блокированную дорогу. Тогда Keshi поймет, что он никогда не должен пользоваться этой дорогой и останется в своем текущем городе на весь день.
  • AmShZ говорит Keshi двигаться. Затем Keshi случайным образом выберет один из городов, до которых можно добраться из его текущего города, и переедет туда. (Город $$$B$$$ достижим из города $$$A$$$, если есть исходящая дорога из города $$$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)$$$  — количество городов и дорог соответственно.

В $$$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 двигаться в течение двух дней.