| Codeforces Round 333 (Div. 1) |
|---|
| Закончено |
В Абсурдистане n городов (пронумерованных от 1 до n) и m двунаправленных железнодорожных перегонов. А ещё там абсурдно простая сеть автотрасс — для любой пары различных городов x и y между ними есть двунаправленная автомобильная дорога тогда и только тогда, когда между ними нет железнодорожного перегона. На перемещение в соседний город по одному железнодорожному перегону или по одной автомобильной дороге уходит ровно один час.
Поезд и автобус одновременно выезжают из города 1. У них обоих один и тот же пункт назначения, город n, и они нигде не останавливаются по пути (кроме итоговой стоянки в городе n). Поезд перемещается только по железнодорожным перегонам, а автобус только по автомобильным дорогам.
Вас попросили составить маршруты для обоих транспортных средств; каждый маршрут может проходить по любой дороге/перегону произвольное количество раз. Одним из наиболее важных пунктов при составлении маршрута является безопасность, поэтому, во избежании несчастных случаев на железнодорожных переездах, поезд и автобус никогда не должны одновременно прибывать в один и тот же город, кроме, возможно, города n.
Через какое наименьшее количество часов оба транспортных могут быть в городе n (максимальное из времён прибытия для автобуса и поезда)? Обратите внимание, что автобус и поезд не обязаны прибыть в город n одновременно, но могут так сделать, если потребуется.
Первая строка входных данных содержит два числа n и m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n - 1) / 2) — количество городов и количество железнодорожных перегонов соответственно.
В каждой из следующих m строк записано по два целых числа u и v, обозначающих наличие железнодорожного перегона между городами u и v (1 ≤ u, v ≤ n, u ≠ v).
Гарантируется, что любые два города соединены не более чем одним железнодорожным перегоном.
Выведите единственное целое число — наименьшее возможное время прибытия последнего из транспортных средств в город n. Если хотя бы одно из двух транспортных средств не сможет добраться до города n, то выведите - 1.
4 2
1 3
3 4
2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
-1
5 5
4 2
3 5
4 5
5 1
1 2
3
В первом примере поезд может поехать по маршруту 
, а автобус по маршруту 
. Обратите внимание, что автобусу и поезду разрешается прибывать в город 4 одновременно.
Во втором примере Абсурдистаном правят железнодорожники. Обычных дорог (не ЖД перегонов) нет, так что автобус никак не может добраться до города 4.
