Задача G. Утки и крокодилы

Автор:В. Глушков, И. Блинов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Парк представляет из себя N полян, соединённых M ненаправленными тропинками одинаковой длинны.

Владельцы крокодилов и уток любят выгуливать своих питомцев по парку. Крокодиловоды заходят в парк через поляну 1, а утководы заходят в парк через поляну с номером N. Прогулка всегда проходит следующим образом: владелец с питомцем идут по какому-то маршруту и при этом посещают каждую поляну и тропинку не более одного раза, а потом возвращаются на стартовую поляну.

Крокодилы часто нападают на уток, и из-за этого владельцы уток крайне недовольны и требуют от администрации парка решить эту проблему. Администрация предложила разделить парк на поляны которые могут посещать только владельцы уток и те которые могут посещать только владельцы крокодилов. Все любят долгие прогулки, а ещё больше справедливость. Поэтому необходимо проложить два не пересекающихся маршрута содержащие минимум 3 вершины (один для утководов, один для владельцев крокодилов) такие, что разница длин маршрутов минимальна.

Формат входных данных

Первая строка входного файла содержит два числа N и M, количество полян и количество тропинок.

Следующие M строк содержат по два числа ui, vi  — номера полян, соединенных i-ой тропинкой.

Формат выходных данных

Выходной файл должен содержать одно целое число  — минимальную разницу длин маршрутов.

В случае если проложить два таких маршрута не представляется возможным, выведите одно число  − 1.

Ограничения

6 ≤ N ≤ 15

6 ≤ M ≤ N * (N − 1)2

Примеры тестов

Стандартный вход Стандартный выход
1
8 10
1 2
1 3
2 3
2 4
3 5
4 5
4 6 
5 7
6 8
7 8
2
2
6 10
1 2
1 3
2 3
2 4
2 5
3 4
3 5
4 5
4 6
5 6
0

0.062s 0.009s 13