AmShZ приехал в Италию из Ирана на концерт Тома Йорка. В Италии есть \(n\) городов с номерами от \(1\) до \(n\) и \(m\) ориентированных дорог с номерами от \(1\) до \(m\). Изначально Keshi находится в городе \(1\) и хочет добраться к дому AmShZ в городе \(n\). Поскольку Keshi не знает карту Италии, AmShZ помогает ему встретиться как можно скорее.
В начале каждого дня AmShZ может отправить Keshi одно из следующих двух сообщений:
AmShZ и Keshi хотят найти наименьшее возможное целое число \(d\), при котором они могут быть уверены, что увидят друг друга через не более чем \(d\) дней. Помогите им найти \(d\).
Выходные данные
Выведите наименьшее возможное целое число \(d\), при котором они могут быть уверены, что увидят друг друга через не более чем \(d\) дней.
Примечание
В первом примере достаточно, чтобы AmShZ отправил сообщение второго типа.
Во втором примере, в первый день, AmShZ блокирует первую дорогу. Поэтому единственным городом, до которого можно добраться из города \(1\), будет город \(4\). Следовательно, на второй день AmShZ может сказать Keshi двигаться, и Keshi прибудет в дом AmShZ.
AmShZ также может сказать Keshi двигаться в течение двух дней.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 2
|
1
|
|
2
|
4 4
1 2
1 4
2 4
1 4
|
2
|
|
3
|
5 7
1 2
2 3
3 5
1 4
4 3
4 5
3 1
|
4
|