A. Два пути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Абсурдистане 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.