F. Гусеница
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Неориентированный граф называется гусеницей, если он является связным графом без циклов, и в нем существует такой путь, что любая вершина находится на расстоянии не более 1 от него. Гусеница может содержать петли, но не может содержать кратных ребер.

На рисунке изображен пример гусеницы:

Вам задан неориентированный граф G с которым можно производить операцию сжатия двух вершин в одну. Для этого выбираются любые две вершины графа a и b (a ≠ b). Из графа удаляются обе эти вершины вместе с их ребрами (инцидентными хотя бы одной из вершин a или b), но добавляется новая вершина w вместе с ребрами вида (x, w) для каждого ребра (a, w) и (b, w). Если в графе существовало ребро (a, b), то оно преобразуется в петлю (w, w). В результате операции слияния могут появляться кратные ребра и петли. Заметим, что эта операция уменьшает количество вершин графа на 1, но оставляет неизменным количество ребер в графе.

Операция сжатия двух вершин может быть неформально описана как объединение двух вершин графа в одну, с естественным преобразованием ребер графа.

С помощью последовательного применения описанной операции можно любой заданный неориентированный граф сделать гусеницей. Напишите программу, которая выведет наименьшее количество операций сжатия, чтобы заданный граф сделать гусеницей.

Входные данные

В первой строке содержится пара целых чисел n, m (1 ≤ n ≤ 2000;0 ≤ m ≤ 105), n — количество вершин в графе, а m — количество ребер в нем. Далее в m строках заданы ребра графа, по одному ребру в строке. Каждая строка содержит пару целых чисел ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi), ai, bi — номера соединяемых ребром вершин. Вершины пронумерованы от 1 до n. Между каждой парой вершин может быть не более одного ребра. Заданный граф не обязательно является связным.

Выходные данные

Выведите искомое наименьшее число операций.

Примеры
Входные данные
4 4
1 2
2 3
3 4
4 2
Выходные данные
2
Входные данные
6 3
1 2
3 4
5 6
Выходные данные
2
Входные данные
7 6
1 2
2 3
1 4
4 5
1 6
6 7
Выходные данные
1