Дорожня система Ужляндії
Велика і прекрасна країна Ужляндія! Вона складається з 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.