Ремонт ланцюга
У Сови був ланцюжок, що складався з n кілець, пронумерованих від 1 до n. Але поки ланцюжок лежав у комоді, він заплутався. Сови хоче виправити ситуацію.
Кожне кільце представляє собою замкнуту петлю з дроту. Кожні два кільця або зчеплені між собою, або ні. Сови звернулася за допомогою до Піна. Він може виконувати дві дії:
Розковати одне з кілець. У цьому випадку воно перестає бути замкнутим, і його можна від'єднати від усіх інших кілець.
Знову запаяти розковане раніше кільце. У цьому випадку воно знову стає замкнутим. Пін може вибрати довільну множину інших кілець, протягнути через них поточне кільце перед запайкою, і таким чином зчепити це кільце з кожним кільцем з вибраної множини.
Наприкінці всі кільця повинні бути запаяні.
Сови хоче, щоб кільце номер 1 було зчеплене з кільцем номер 2, 2 з 3, ..., n - 1 з n. Іншими словами, щоб були зчеплені кільця з номерами i та i + 1 для всіх i ∈ [1, n - 1]. Жодні інші пари кілець не повинні бути зчеплені.
Допоможіть Піну визначити мінімальну кількість дій, які йому доведеться виконати, щоб полагодити ланцюжок.
Вхідні дані
У першому рядку дано два цілих числа 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]) - номери зчеплених кілець.
Гарантується, що у вхідних даних кожна неупорядкована пара кілець зустрічається максимум один раз.
Вихідні дані
Виведіть одне ціле число - мінімальну кількість дій, які повинен зробити Пін, щоб полагодити ланцюжок.
Примітка
У першому прикладі Пін може розковати кільце номер 3. Тоді воно від'єднається від обох інших кілець. Потім він може запаяти кільце номер 3 назад, зчепивши його тільки з кільцем номер 2.
У другому прикладі Пін може розковати кільце номер 2, потім запаяти його назад, з'єднавши з кільцями 1 і 3. Потім розковати кільце номер 4 і запаяти назад, з'єднавши з кільцями 3 і 5.