Ant-Man is the latest superhero on the stage. Like most superheroes, he has got unique powers – besides shrinking to the size of an insect, he can control ants through his suit. As usual, Ant-Man should use his powers only for the greater good (e.g., world peace, saving mankind, or supervising programming contests), but more often than not, he uses them to impress his girlfriend, Wasp. This time he has invited Wasp over for some Colombian coffee. Not being used to the strong taste, she wants to sweeten it, but this being a programming contest, there’s one little problem: the ants have taken all the sugar to their nest while Ant-Man wasn’t looking. The ants’ nest is unlike any other: it has got only one entrance and one (different) exit, and comprises a network of tunnels connecting them, with several intersections and branching. Since there are many ants living in the tunnels, every tunnel may be run only in a predetermined direction, and there is no path of tunnels from any intersection to itself, no dead ends, and no inaccessible intersections. The ants are keeping a sugar cube at every intersection. Wanting to impress Wasp some more, he will use his ants to bring his sugar back instead of going in himself, and he will do it with the minimum possible number of ants. Each ant is strong enough to carry an unlimited amount of sugar cubes at the same time, but Ant-Man doesn’t want them to feel like tools, so he will not order any ant to re-enter the nest after its sugar run is done. Ant-Man has asked his old cellmate for help in performing this task, and as usual, he “knew someone who knows someone” who has relayed this problem to you. Now you must calculate the minimum possible number of ants needed to bring back all the sugar. Input The input consists of several test cases. Each case begins with a line containing two blank-separated integers N and M (2 ≤ N ≤ 100 and 1 ≤ M ≤ 5000), which represent the number of intersections and the number of tunnels in the nest, respectively; the entrance and exit points are counted as intersections. Next come M lines with two blank-separated integers u and v (0 ≤ u ≤ N − 1, 0 ≤ v ≤ N − 1, and u ̸= v), meaning that there is a tunnel from intersection u to intersection v (running in that direction). Output For each test case print a line containing the minimum number of ants needed to recover all the sugar. Sample Input 9 12 01 02 13 14 24 25 36 46 47 57
2/2 68 78 Sample Output 3