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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

6 ≤ N ≤ 15

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

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

8 10
1 2
1 3
2 3
2 4
3 5
4 5
4 6 
5 7
6 8
7 8

2

6 10
1 2
1 3
2 3
2 4
2 5
3 4
3 5
4 5
4 6
5 6

0