Дорожная система Ужляндии
Великая и прекрасная страна Ужляндия! Она состоит из N городов, пронумерованных от 1 до N, и M дорог между ними. Каждая дорога соединяет два разных города и обеспечивает возможность перемещения между ними. Дорожная система в Ужляндии весьма специфична. Все дороги имеют двустороннее движение, и между каждой парой городов может быть не более одной дороги.
С давних времен дорожная система Ужляндии удовлетворяет свойству нечетности. Это свойство поддерживалось по религиозным соображениям древних ужлянцев, а в настоящее время сохраняется как дань традиции, подобно нечетному количеству цветов в праздничном букете. Сформулируем свойство нечетности:
Последовательность номеров городов C_1,..., C_K(K ≥ 2) называется путем, если для любой соседней пары элементов последовательности C_i, C_i_{+1} (C_i ≠ C_i_{+1}, для 1 ≤ i < K) существует дорога между городами с номерами C_i и C_i_{+1}. Если C_1 = C_K, то такой путь называется замкнутым. Длину пути C_1, ..., C_K будем считать равной длине последовательности, то есть K. Итак, правило нечетности гласит, что все замкнутые пути в Ужляндии имеют нечетную длину, то есть не существует замкнутого пути четной длины.
Дорожная сеть, изображенная на рисунке №1, обладает свойством нечетности, а дорожная система на рисунке №2 не обладает этим свойством из-за наличия в ней замкнутого пути четной длины 4: 1 2 4 1.
Недавно Министр транспорта Ужляндии решил, что существующая дорожная система неэффективна, и необходимо построить несколько новых дорог. При этом новая дорожная система, полученная из старой добавлением некоторого числа дорог, должна сохранять свойство нечетности. Все новые дороги должны соединять разные города. Кроме того, в новой дорожной сети между каждой парой городов должна проходить не более одной дороги.
Для улучшения эффективности дорожной системы было выделено много средств, поэтому Министр Ужляндии решил построить как можно больше новых дорог, чтобы полученная дорожная система соответствовала описанным выше условиям. Однако эта задача оказалась довольно сложной, и министерство транспорта Ужляндии решило обратиться к Вам за консультацией.
Итак, вам дано описание существующей дорожной сети. Вам необходимо определить максимальное количество дорог, которое можно добавить к существующей сети, не нарушая вышеописанных свойств.
Формат входных данных: Первая строка входного файла содержит целые числа N (1 ≤ N ≤ 10 000) и M (0 ≤ M ≤ 100000). Следующие M строк описывают дороги Ужляндии. В каждой строке находится описание ровно одной дороги. Каждая дорога описывается двумя целыми числами X и Y (1 ≤ X, Y ≤ N, X ≠ Y). Эти числа соответствуют номерам городов, связанных дорогой. Города нумеруются последовательно целыми числами от 1 до N.
Гарантируется, что заданная дорожная система удовлетворяет свойству нечетности, а также любые два города связаны не более чем одной дорогой.
Формат выходных данных: Выходной файл должен содержать одно целое число - максимальное количество дорог, которое можно добавить в существующую дорожную сеть.
Пояснение к примерам:
Дорожная сеть из первого примера приведена на рисунке № 1. Заданная дорожная сеть из второго примера представлена на рисунке №3, а ее состояние после добавления к ней новых дорог изображено на рисунке №4.
Во втором примере можно добавить 5 новых дорог: 2 5, 1 4, 1 6, 3 4, 3 6.