e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Королівство

Королівство

У казковому королевстві N міст. Деякі пари міст з’єднано дорогами, причому одну і ту саму пару міст можуть з’єднувати декілька доріг. Зовні міст дороги не перетинаються. По кожній дорозі можна їхати в будь-якому напрямку. Допоможіть королю визначити, скільки ще доріг потрібно побудувати у королівстві, щоб Його Величність зміг зробити подорож по всіх дорогах, не проїзджаючи двічі по жодній з них. Звичайно (див приклад нижче), він має бажання відвідати кожне місто. Подорож короля повинна починатись і закінчуватись в одному і тому самому місті.

Вхідні дані

Ви вводите спочатку кількість міст у королівстві N (1 N 100)і кількість пар міст К (1 K 10000). Потім в К групах по 3 числа ви вводите номери міст і кількості доріг, що їх з'єднують (всі числа не перевищують 100). Всі числа розділені пропуском.

Вихідні дані

Ви виводите мінімально можливу кількість доріг.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
7 6 1 2 1 1 3 1 4 1 3 4 2 5 3 4 3 5 6 2
Вихідні дані #1
3