[Usaco2007 Mar]Ranking the Cows 奶牛排名
时间限制：5s 空间限制：64MB
题目描述
农夫约翰有N(1≤N≤1000)头奶牛，每一头奶牛都有一个确定的独一无二的正整数产奶率．约翰想要让这些奶牛按产奶率从高到低排序． 约翰已经比较了M(1≤M≤10000)对奶牛的产奶率，但他发现，他还需要再做一张关于另外C对奶牛的产奶率比较，才能推断出所有奶牛的产奶率排序．请帮他确定C的最小值．
输入格式
第1行包含两个用空格分开的整数N和M.接下来M行，每行有两个用空格分开的整数X和Y(1≤X，y≤1000)，表示奶牛X的产奶率高于奶牛Y.
输出格式
C的最小值．
样例输入
5 5 2 1 1 5 2 3 1 4 3 4 INPUT DETAILS: FJ is comparing 5 cows and has already determined that cow 2 > cow 1, cow 1 > cow 5, cow 2 > cow 3, cow 1 > cow 4, and cow 3 > cow 4 (where the '>' notation means "produces milk more quickly").
样例输出
3
提示
从输入样例中可以发现，约翰已经知道的排名有奶牛2>奶牛1>奶牛5和奶牛2>奶牛3>奶牛4，奶牛2排名第一．但是他还需要知道奶牛1的名次是否高于奶牛3来确定排名第2的奶牛，假设奶牛1的名次高于奶牛3．接着，他需要知道奶牛4和奶牛5的名次，假设奶牛5的名次高于奶牛4．在此之后，他还需要知道奶牛5的名次是否高于奶牛3．所以，他至少仍需要知道3个关于奶牛的排名．
题目来源
Gold