e-olymp
Соревнования

IOI 2019 Azerbaijan Team Selection Contest (Day1 + Day2)

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

В городе Баку есть n городов, соединённых m двусторонними дорогами. Дороги не могут соединять город с самим собой, и каждая пара городов соединяется не более чем одной дорогой. Не гарантируется, что из любого города можно доехать до любого другого, используя только имеющиеся дороги.

Мер города Гаджи Ибрахим решил внести изменения в систему дорожных путей и дал указание министерству транспорта заняться данной реформой. Теперь каждая дорога должна стать односторонней (вести только из одного города в другой).

Чтобы не вызвать большого недовольства у жителей, необходимо провести реформу так, чтобы оставалось как можно меньше обособленных городов. Город считается обособленным, если в него не входит ни одна дорога, при этом выходящие из этого города дороги допустимы.

Помогите Гаджи Ибрагиму найти минимальное количество обособленных городов после проведения реформы.

Входные данные

В первой строке входных данных следуют два целых положительных числа n и m — количество городов и дорог в Берляндии (2 ≤ n ≤ 100000, 1 ≤ m ≤ 100000).

В следующих m строках содержатся описания дорог: i-я дорога задаётся двумя различными целыми числами xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi), где xi и yi равны номерам городов, которые соединяет i-я дорога.

Гарантируется, что между каждой парой городов не может быть более одной дороги, но не гарантируется, что из любого города можно доехать до любого другого, используя только дороги.

Выходные данные

Выведите единственное число — минимальное количество обособленных городов после проведения реформы.

Лимит времени 1 секунда
Лимит использования памяти 256 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