Починка цепочки

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

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

• Расковать одно из звеньев. При этом, оно перестает быть замкнутым кольцом, и поэтому его можно отсоединить от всех остальных звеньев.
• Обратно запаять раскованное ранее звено. При этом, оно обратно становится замкнутым кольцом. Пин может выбрать произвольное множество других звеньев, продеть через них текущее звено перед запайкой, и таким образом сцепить это звено с каждым звеном из выбранного множества.

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

Совунья хочет, чтобы звено номер $1$ было сцепленно со звеном номер $2$, $2$ с $3$, \dots, $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$ обратно, сцепив его только со звеном номер $2$.

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