| Codeforces Round 346 (Div. 2) |
|---|
| Закончено |
В Берляндии есть n городов, соединённых m двусторонними дорогами. Дороги не могут соединять город с самим собой, и каждая пара городов соединяется не более чем одной дорогой. Не гарантируется, что из любого города можно доехать до любого другого, используя только имеющиеся дороги.
Президент Берляндии решил внести изменения в систему дорожных путей и дал указание министерству транспорта заняться данной реформой. Теперь каждая дорога должна стать односторонней (вести только из одного города в другой).
Чтобы не вызвать большого недовольства у жителей, необходимо провести реформу так, чтобы оставалось как можно меньше обособленных городов. Город считается обособленным, если в него не входит ни одна дорога, при этом выходящие из этого города дороги допустимы.
Помогите министерству транспорта найти минимальное количество обособленных городов после проведения реформы.
В первой строке входных данных следуют два целых положительных числа n и m — количество городов и дорог в Берляндии (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000).
В следующих m строках содержатся описания дорог: i-я дорога задаётся двумя различными целыми числами xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi), где xi и yi равны номерам городов, которые соединяет i-я дорога.
Гарантируется, что между каждой парой городов не может быть более одной дороги, но не гарантируется, что из любого города можно доехать до любого другого, используя только дороги.
Выведите единственное число — минимальное количество обособленных городов после проведения реформы.
4 3
2 1
1 3
4 3
1
5 5
2 1
1 3
2 3
2 5
4 3
0
6 5
1 2
2 3
4 5
4 6
5 6
1
В первом примере допустима следующая ориентация дорог: 
, 
, 
.
Во втором примере: , 
, 
, 
, .
В третьем примере: , , 
, 
, 
.
