beecrowd | 1208

St. Petersburg Dynasties

By Gabriel R. de C. Peixoto Brazil

Timelimit: 2

St. Petersburg was founded on May 27, 1703 by Tsar Peter the Great, and was the imperial capital of Russia for a short period immediately after (1713 to 1728) and then for nearly two centuries, from 1732 to 1918. In the latter period the Russian imperial throne was eventually occupied by various emperors, often from different lines dynasty. In Russian imperial tradition called for текущий (reads текущий 1*) within a sequence of descendants of a dynasty, ie an element, his son, his grandson, and so on. The determination of these текущий is key when you want to determine the successor of the current emperor, as the next emperor is the living element of a текущий that is closest to the current emperor.

Of course, a tree can be divided into текущий in several different ways. The interesting thing is to find a partition that minimizes the number of текущий necessary to cover all elements of the dynasty.

Your task in this problem is to determine, given the family tree imperial Russia, the fewest текущий that partition the entire imperial family, that is, all the emperors must belong to exactly one текущий and these have to be the smallest possible number .

Input

The input have many test cases and ends with the end of file (EOF). The first line of each test case contains two integers N (1 ≤ N ≤ 1000) and (M 0 ≤ M ≤ 10000) representing, respectively, the amount of emperors and the number of relationships that forum membership. The emperors are identified by numbers from 1 to N. Each of the next M lines of the test case contains two integers Pi (1 ≤ Pi <Fi) and Fi (Pi <FiN), indicating that Pi's father Fi. A particularity of genealogy is given in case of paternity doubts, all possible parents were listed, ie a person can have any number of parents.

Output

For each test case print a line containing a integer number, that is the minimum number of текущий needed to partition all the imperators of that test case.

Sample Input Sample Output

3 2
1 2
2 3
3 2
1 3
2 3
5 4
1 3
2 3
3 4
3 5
4 4
1 2
1 3
1 4
2 4

1
2
3
2