28630번 - Починка цепочки 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 6 | 6 | 2 | 100.000% |
문제
У Совуньи была цепочка, состоявшая из $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$).
Гарантируется, что во входных данных каждая неупорядоченная пара звеньев встречается максимум один раз.
출력
Выведите одно целое число --- минимальное количество действий, которые должен сделать Пин, чтобы починить цепочку.
예제 입력 1
3 3 1 2 2 3 3 1
예제 출력 1
2
예제 입력 2
5 0
예제 출력 2
4
예제 입력 3
1 0
예제 출력 3
0
노트
В первом примере Пин может расковать звено номер $3$. Тогда оно отсоединится от обоих оставшихся звеньев. А затем, запаять звено номер $3$ обратно, сцепив его только со звеном номер $2$.
Во втором примере Пин может расковать звено номер $2$, затем запаять его обратно соединив со звеньями $1$ и $3$. А затем, расковать звено номер $4$ и запаять обратно, соединив со звеньями $3$ и $5$.