#699. 1703. [Usaco2007 Mar]Ranking the Cows 奶牛排名

1703. [Usaco2007 Mar]Ranking the Cows 奶牛排名

#1703. [Usaco2007 Mar]Ranking the Cows 奶牛排名

题目描述

农夫约翰有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个关于奶牛的排名.