Починка цепочки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Совуньи была цепочка, состоявшая из $$$n$$$ звеньев, пронумерованных от $$$1$$$ до $$$n$$$. Но пока цепочка валялась в комоде, она вся запуталась. Совунья хочет исправить ситуацию.

Каждое звено представляет из себя кольцо из проволоки. Каждые два звена либо сцеплены друг с другом, либо нет. Совунья обратилась за помощью к Пину. Он может делать два действия:

В конце все звенья должны быть запаянными.

Совунья хочет, чтобы звено номер $$$1$$$ было сцепленно со звеном номер $$$2$$$, $$$2$$$ с $$$3$$$, ..., $$$n - 1$$$ с $$$n$$$. Иными словами, чтобы были сцеплены звенья с номерами $$$i$$$ и $$$i + 1$$$ для всех $$$i \in [1, n - 1]$$$. А никакие другие пары звеньев не должны быть сцеплены.

Помогите Пину определить минимальное количество действий, которые ему придется выполнить, чтобы починить цепочку.

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — количество звеньев и количество пар изначально сцепленных звеньев ($$$1 \le n \le 40$$$, $$$0 \le m \le \frac{n \cdot (n - 1)}{2}$$$).

В следующих $$$m$$$ строках дано по два целых числа $$$a_i$$$ и $$$b_i$$$ — номера сцепленных звеньев ($$$1 \le a_i, b_i \le n$$$; $$$a_i \neq b_i$$$).

Гарантируется, что во входных данных каждая неупорядоченная пара звеньев встречается максимум один раз.

Выходные данные

Выведите одно целое число — минимальное количество действий, которые должен сделать Пин, чтобы починить цепочку.

Примеры

Входные данные
3 3
1 2
2 3
3 1
Выходные данные
2
Входные данные
5 0
Выходные данные
4
Входные данные
1 0
Выходные данные
0

Примечание

В первом примере Пин может расковать звено номер $$$3$$$. Тогда оно отсоединится от обоих оставшихся звеньев. А затем, запаять звено номер $$$3$$$ обратно, сцепив его только со звеном номер $$$2$$$.

Во втором примере Пин может расковать звено номер $$$2$$$, затем запаять его обратно соединив со звеньями $$$1$$$ и $$$3$$$. А затем, расковать звено номер $$$4$$$ и запаять обратно, соединив со звеньями $$$3$$$ и $$$5$$$.