Чергування
У Міністерстві охорони здоров’я прийняли рішення – виконати санітарну обробку вулиць міста Д. Для цієї мети була зібрана бригада високопрофесійних лікарів. У місті є N лікарень, які пов’язані між собою M шляхами. Аби обробити шляхи між лікарнями, направляють бригаду, яка повинна проїхати рівно один раз по кожному із цих шляхів і потім повернутися назад. Оскільки це може бути неможливим, то бригаду дозволяється телепортувати. Операція телепортації дуже дорого коштує Міністерству, тому таких операцій повинно бути якнайменше. Між лікарнями може бути декілька шляхів, в тому числі можуть бути шляхи, що з'єднують лікарню саму з собою. Бригада може почати свій шлях від будь-якої лікарні. Складну задачу підрахунку телепортацій Міністерство доручило Ватсону. Він активізував усі свої чіпи нейронної мережі для того, щоб її вирішити та заглибився у розрахунки. Рибка визвалася допомогти та запропонувала – можливо є більш простий спосіб вирішення задачі?
Вхідні дані
В першому рядку вказано два цілих числа N та M (1 ≤ N, M < 10^5).
Далі M рядків, що містять два цілих числа: i j – що описують шлях між лікарнями, i та j (1 ≤ i, j ≤ N).
Вихідні дані
Розрахувати мінімальну кількість необхідних телепортацій.