eolymp
bolt
Try our new interface for solving problems
Problems

Roads renewal

Roads renewal

The Berland country has $n$ cities connected by $m$ two-way roads. Roads cannot connect a city to itself, and each pair of cities is connected with at most one road. It is not guaranteed that it is possible to get from any city to any other using only the available roads. Mayor Haji Ibrahim decided to make changes to the road system and instructed the Ministry of Transport to take up this reform. Now each road should become one-way (lead only from one city to another). In order not to cause great discontent among the inhabitants, it is necessary to carry out a reform so that there are as few isolated cities as possible. A city is considered \textbf{isolated} if no road enters it, while roads leaving this city are allowed. Help Haji Ibrahim find the minimum number of isolated cities after the reform. \InputFile The first line contains two positive integers $n$ and $m~(2 \le n \le 10^5, 1 \le m \le 10^5)$ --- the number of cities and roads in Berland. The following $m$ lines contain descriptions of the roads: $i$-th road is given by two different integers $x_i, y_i~(1 \le x_i, y_i \le n, x_i \ne y_i)$, where $x_i$ and $y_i$ equal to the numbers of the cities that $i$-th road connects. It is guaranteed that there cannot be more than one road between each pair of cities, but it is not guaranteed that it is possible to get from any city to any other using only the available roads. \OutputFile Print one number --- the minimum number of isolated cities after the reform.
Time limit 1 second
Memory limit 128 MiB
Input example #1
4 3
2 1
1 3
4 3

Output example #1
1
Input example #2
5 5
2 1
1 3
2 3
2 5
4 3

Output example #2
0
Source İOİ 2019 Azərbaycan komandasına seçim turu