Дорожня система Узляндії#7242
Узляндія — це чудова країна з містами, пронумерованими від до , які з'єднані дорогами. Кожна дорога з'єднує два різні міста та дозволяє пересування в обидва боки. Між будь-якою парою міст може бути не більше однієї дороги.
З давніх часів дорожня система Узляндії підкоряється особливій властивості, яка називається непарність. Спочатку це підтримувалося з релігійних причин, і традиція збереглася донині, так само, як звичай дарувати непарну кількість квітів у букеті.
Визначимо властивість непарності:
Послідовність номерів міст C_1, \ldots, C_K (K \geq 2) називається шляхом, якщо для кожної пари сусідніх міст C_i, C_{i+1} (C_i \neq C_{i+1}, 1 \leq i < K) існує дорога, що з'єднує міста C_i та C_{i+1}. Якщо C_1 = C_K, шлях називається замкненим. Довжина шляху C_1, \ldots, C_K дорівнює .
Правило непарності стверджує, що в Узляндії всі замкнені шляхи повинні мати непарну довжину. Тобто, жодного замкненого шляху парної довжини не існує.
Дорожня система на малюнку задовольняє властивості непарності. Система на малюнку цій властивості не задовольняє, оскільки в ній існує замкнений шлях парної довжини : 1 \to 2 \to 4 \to 1.
Нещодавно міністр транспорту Узляндії вирішив підвищити ефективність мережі доріг, збудувавши додаткові дороги. Однак нова мережа повинна й надалі задовольняти властивість непарності. Усі нові дороги повинні з'єднувати різні міста, і між будь-якою парою міст також повинно бути не більше однієї дороги.
На цей проект виділено значний бюджет, тому міністр хоче додати якомога більше нових доріг, не порушуючи властивість непарності. Проте це складне завдання, тому Міністерство транспорту звертається до вас за допомогою.
Вам надано опис поточної дорожньої мережі. Ваше завдання — визначити, яку максимальну кількість доріг можна додати, не порушуючи властивість непарності.
У першому рядку вказано цілі числа (1 \leq N \leq 10\ 000) і (0 \leq M \leq 100\ 000).
У наступних рядках описані дороги Узляндії. Кожен рядок містить два цілі числа і (1 \leq X, Y \leq N, X \neq Y) — існує дорога між містами і .
Гарантується, що існуюча система доріг задовольняє властивість непарності, і між будь-якими двома містами не більше однієї дороги.
Виведіть єдине ціле число — максимальну кількість доріг, яку можна додати до існуючої мережі доріг.
Приклад 1
Дорожню мережу з першого прикладу зображено на малюнку . Мережу з другого прикладу показано на малюнку , а її стан після додавання нових доріг — на малюнку .
У другому прикладі можна додати нових доріг: -, -, -, -, -.