Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Kingdom

Задача Kingdom

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

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

Приклад.

Введення> 7 6 1 2 1 1 3 1 4 1 3 4 2 5 3 4 3 5 6 2
Виведення> 3


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"