У Фермера Джона есть \(N\) коров, помеченных числами от \(1\) до \(N\) (\(2\le N\le 16\)).
Отношение дружбы между этими коровами может быть смоделировано ненаправленным графом
с \(M\) (\(0\le M\le N(N-1)/2\)) ребрами. Две коровы являются друзьями, если и только если
между ними есть ребро в этом графе.
За одну операцию Вы можете добавить или удалить одно ребро в этом графе.
Посчитайте минимальное количество операций, которое требуется выполнить,
чтобы обеспечить следующее свойство в этом графе:
Если коровы \(a\) и \(b\) - друзья, тогда для любой другой коровы \(c\)
по крайней мере одна из коров \(a\) и \(b\) является другом коровы \(c\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(M\).
Каждая из следующих \(M\) строк содержит пару чисел \(a\) и \(b\) (\(1\le a<b\le N\)).
Никакая пара друзей не повторится.
ФОРМАТ ВЫВОДА (на экран / stdout):
Количество ребер, которые требуется удалить или добавить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 2
|
1
|