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

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

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

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

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