favorite We need a little bit of your help to keep things running, click on this banner to learn more

Strong Connected Components


Dominoes are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominoes falling again.

Your task is to determine, given the layout of some domino tiles, the minimum number of dominoes that must be knocked down by hand in order for all of the dominoes to fall.


The first line contains two integers, each no larger than 100000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.


Print a line containing one integer, the minimum number of dominoes that must be knocked over by hand in order for all the dominoes to fall.

Time limit 1 seconds
Memory limit 64 MiB
Input example #1
3 2
1 2
2 3
Output example #1
Source Summer School 2010, Sebastopol, Day M.Medvedev