eolymp
bolt
Try our new interface for solving problems
Məsələlər

Королевство

Королевство

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

В сказочном королевстве N городов. Некоторые пары городов соединены дорогами, причем одна и та самая пара городов могут соединять несколько дорог. Вне городов дороги не пересекаются. По каждой дороге можно ехать в любом направлении. Помогите королю определить, скольои еще дорог нужно построить в королевстве, чтобы Его Величество смог совершить путешествие по всем дорогам, не прооезжая дважды ни по одной из них. Обычно (см. пример), он имеет желание посетить каждый город. Путешествие короля должно начинатся и заканчиватся в одном и том же городе.

Giriş verilənləri

Вы вводите сначала количество городов в королевстве N (1 N 100) и количество пар городов К (1 K 10000). Затем в К группах по 3 числа вы вводите номера городов и количества дорог, их соединяющих (все числа не превышают 100). Все числа розделены пробелом.

Çıxış verilənləri

Вы выводите минимально возможное количество дорог.

Nümunə

Giriş verilənləri #1
7 6 1 2 1 1 3 1 4 1 3 4 2 5 3 4 3 5 6 2
Çıxış verilənləri #1
3