
ZOJ Problem Set  3795
Suppose there are N people in ZJU, whose ages are unknown. We have some messages about them. The ith message shows that the age of person s_{i} is not smaller than the age of person t_{i}. Now we need to divide all these N people into several groups. One's age shouldn't be compared with each other in the same group, directly or indirectly. And everyone should be assigned to one and only one group. The task is to calculate the minimum number of groups that meet the requirement.
InputThere are multiple test cases. For each test case: The first line contains two integers N(1≤ N≤ 100000), M(1≤ M≤ 300000), N is the number of people, and M is is the number of messages. Then followed by M lines, each line contain two integers s_{i} and t_{i}. There is a blank line between every two cases. Process to the end of input. OutputFor each the case, print the minimum number of groups that meet the requirement one line. Sample Input4 4 1 2 1 3 2 4 3 4 Sample Output3 Hintset1= {1}, set2= {2, 3}, set3= {4} Author: LUO, Jiewei Source: ZOJ Monthly, June 2014 