Полагодження ланцюжка#11060

Полагодження ланцюжка

1 секунда

128 мегабайтів

Середня

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

Кожна ланка являє собою кільце з дроту. Кожні дві ланки або переплетені одна з одною, або ні. Сова звернулася за допомогою до Піна. Він може виконувати дві дії:

Розкувати одну з ланок. При цьому ланка перестає бути замкнутим кільцем, і тому її можна від'єднати від усіх інших ланок.
Знову запаяти раніше розковану ланку. При цьому, вона знову стає замкнутим кільцем. Пін може вибрати довільну множину інших ланок, протягти через них поточну ланку перед запаюванням і таким чином з'єднати цю ланку з кожною ланкою з вибраної множини.

Наприкінці всі ланки повинні бути запаяними.

Сова хоче, щоб ланка номер $1$ була з'єднана з ланкою номер $2$ , $2$ з $3$ , ..., $n - 1$ n - 1 з $n$ . Іншими словами, щоб були з'єднані ланки з номерами $i$ та $i + 1$ i + 1 для всіх $i \in [1, n - 1]$ i \in [1, n - 1]. І ніякі інші пари ланок не повинні бути з'єднані.

Допоможіть Піну визначити мінімальну кількість дій, які йому доведеться виконати, щоб полагодити ланцюжок.

Вхідні дані

У першому рядку задано два цілих числа $n$ і $m (1 \leq n \leq 40, 0 \leq m \leq n \cdot (n - 1) /2)$ m~(1 \le n \le 40, 0 \le m \le n \cdot (n - 1) / 2) — кількість ланок і кількість пар спочатку з'єднаних ланок.

У наступних $m$ рядках дано по два цілі числа $a_{i}$ a_i і $b_{i} (1 \leq a_{i}, b_{i} \leq n, a_{i} \neq = b_{i})$ b_i~(1 \le a_i, b_i \le n, a_i \ne b_i) — номери з'єднаних ланок.

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

Вихідні дані

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

Приклади

У першому прикладі Пін може розкувати ланку номер $3$ . Тоді вона від'єднається від обох інших ланок. А потім запаяти ланку номер $3$ назад, з'єднавши її тільки з ланкою номер $2$ .

У другому прикладі Пін може розкувати ланку номер $2$ , потім запаяти її назад, з'єднавши з ланками $1$ і $3$ . А потім розкувати ланку номер $4$ і запаяти назад, з'єднавши з ланками $3$ і $5$ .

Приклад 1

Приклад 2

Приклад 3