Починка цепочки
У Совуньи была цепочка, состоявшая из n звеньев, пронумерованных от 1 до n. Но пока цепочка валялась в комоде, она вся запуталась. Совунья хочет исправить ситуацию.
Каждое звено представляет из себя кольцо из проволоки. Каждые два звена либо сцеплены друг с другом, либо нет. Совунья обратилась за помощью к Пину. Он может делать два действия:
Расковать одно из звеньев. При этом, оно перестает быть замкнутым кольцом, и поэтому его можно отсоединить от всех остальных звеньев.
Обратно запаять раскованное ранее звено. При этом, оно обратно становится замкнутым кольцом. Пин может выбрать произвольное множество других звеньев, продеть через них текущее звено перед запайкой, и таким образом сцепить это звено с каждым звеном из выбранного множества.
В конце все звенья должны быть запаянными.
Совунья хочет, чтобы звено номер 1 было сцепленно со звеном номер 2, 2 с 3, . . . , n - 1 с n. Иными словами, чтобы были сцеплены звенья с номерами i и i + 1 для всех i ∈ [1, n - 1]. А никакие другие пары звеньев не должны быть сцеплены.
Помогите Пину определить минимальное количество действий, которые ему придется выполнить, чтобы починить цепочку.
Giriş verilənləri
В первой строке даны два целых числа n и m (1 ≤ n ≤ 40, 0 ≤ m ≤ n * (n - 1) / 2) - количество звеньев и количество пар изначально сцепленных звеньев.
В следующих m строках дано по два целых числа a[i]
и b[i]
(1 ≤ a[i]
, b[i]
≤ n, a[i]
≠ b[i]
) - номера сцепленных звеньев.
Гарантируется, что во входных данных каждая неупорядоченная пара звеньев встречается мак- симум один раз.
Çıxış verilənləri
Выведите одно целое число - минимальное количество действий, которые должен сделать Пин, чтобы починить цепочку.
Замечание
В первом примере Пин может расковать звено номер 3. Тогда оно отсоединится от обоих оставшихся звеньев. А затем, запаять звено номер 3 обратно, сцепив его только со звеном номер 2.
Во втором примере Пин может расковать звено номер 2, затем запаять его обратно соединив со звеньями 1 и 3. А затем, расковать звено номер 4 и запаять обратно, соединив со звеньями 3 и 5.