Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3630

Time Limit: 2 Seconds      Memory Limit: 32768 KB

It is a war between Country Alpha and Country Beta. Country Alpha gets following information about Country Beta:

Country Beta has n (2 <= n <= 100) cities numbered from 0 to n-1. Each city has a transmitter and a receiver. One city is able to transmit important information by its transmitter to another city. Meanwhile, if there's information transmitted to one city, it is able to receive the information by its receiver. Of course, it is OK that one city doesn't transmit any information to another city and that if no information transmitted to one city, the city receives no information. Thus, a quantity of cities are able to constitute a group. In a group, any city is able to transmit the information to any city in the group directly or indirectly. Of course, one city belongs to only one group.

Now, Country Alpha wants to demolish one city of Country Beta. Thus, Alpha will make the number of cities in the largest group as small as possible.


Ther are multiple test cases (about 200 cases). There is a blank line between each case.

The first line of each case contains two positive integers, n and m (0 <= m <= 9900), in which m indicates the number of the path(es) of the information from one city to another. In each line of following m line(s), there are two positive integers, s, t, indicating that some information is from City s to City t. No same pair of (s,t).


Output the least number of cities in a group, which is the largest group after Country Alpha's attack. By the way, a group must consist of at least two cities, that is, one city is not able to be considered as a group. If there is no group, output 0.

Sample Input

2 2
0 1
1 0

Sample Output


Author: LI, Zezhou
Contest: ZOJ Monthly, July 2012
Submit    Status