26208번 - Helping the Transit 다국어

The president of Nlogonia decided, by decree, that all the streets of Nlogonia should be one-way. Due to the lack of knowledge of elementary science, there was no proper planning for the changes. After the new system came in place, people would not be able to go to work, or would not be able to return home from work, for example. As a result, there was chaos and riots in lots of cities.

The president was impeached and the new administration of the country hired a team of scientists to solve the problem. In turn, the committee hired you, an expert in complexity of algorithms, to help them with the efficient computation of solutions.

So, for each city, you are given the reference points of the city, and the one-way streets, each of which connects two reference points. Your task is to determine the minimum number of one-way bridges that must be built in order to have full connectivity in the city. Each bridge should also connect two reference points.

The first line of the input contains two integers, $N$ and $M$ ($1 ≤ N ≤ 10^4$, $1 ≤ M ≤ 10^6$), where $N$ is the number of reference points and $M$ is the number of streets. Each one of the next $M$ lines contains two integers, $R$ and $S$, $1 ≤ R, S ≤ N$, $R \ne S$, that corresponds to a street connecting $R$ to $S$, so that every vehicle in that street must move away from $R$, towards $S$.

Your program must print a single line containing the minimum number of bridges that are necessary to make the inhabitants happy.