У Совуньи была цепочка, состоявшая из $$$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$$$.