eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Обновление дорог

Обновление дорог

В Берляндии есть $n$ городов, соединённых $m$ двусторонними дорогами. Дороги не могут соединять город с самим собой, и каждая пара городов соединяется не более чем одной дорогой. Не гарантируется, что из любого города можно доехать до любого другого, используя только имеющиеся дороги. Мер города Гаджи Ибрахим решил внести изменения в систему дорожных путей и дал указание министерству транспорта заняться данной реформой. Теперь каждая дорога должна стать односторонней (вести только из одного города в другой). Чтобы не вызвать большого недовольства у жителей, необходимо провести реформу так, чтобы оставалось как можно меньше обособленных городов. Город считается \textbf{обособленным}, если в него не входит ни одна дорога, при этом выходящие из этого города дороги допустимы. Помогите Гаджи Ибрагиму найти минимальное количество обособленных городов после проведения реформы. \InputFile Первая строка содержит два натуральных числа $n$ и $m~(2 \le n \le 10^5, 1 \le m \le 10^5)$ --- количество городов и дорог в Берляндии. В следующих $m$ строках содержатся описания дорог: $i$-я дорога задаётся двумя различными целыми числами $x_i, y_i~(1 \le x_i, y_i \le n, x_i \ne y_i)$, где $x_i$ и $y_i$ равны номерам городов, которые соединяет $i$-я дорога. Гарантируется, что между каждой парой городов не может быть более одной дороги, но не гарантируется, что из любого города можно доехать до любого другого, используя только имеющиеся дороги. \OutputFile Выведите одно число --- минимальное количество обособленных городов после проведения реформы.
Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4 3
2 1
1 3
4 3

Выходные данные #1
1
Входные данные #2
5 5
2 1
1 3
2 3
2 5
4 3

Выходные данные #2
0
Источник İOİ 2019 Azərbaycan komandasına seçim turu