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

[Usaco2007 Mar]Ranking the Cows 奶牛排名

题目描述

农夫约翰有 nn 头奶牛,每一头奶牛都有一个确定的独一无二的正整数产奶率。约翰想要让这些奶牛按产奶率从高到低排序。 约翰已经比较了 mm 对奶牛的产奶率,但他发现,他还需要再做一张关于另外 cc 对奶牛的产奶率比较,才能推断出所有奶牛的产奶率排序。请帮他确定 cc 的最小值。

输入格式

第一行包含两个用空格分开的整数 nnmm
接下来 mm 行,每行有两个用空格分开的整数 mmyy,表示奶牛 xx 的产奶率高于奶牛 yy

输出格式

cc 的最小值。

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

样例说明

FJ is comparing 55 cows and has already determined that cow 22 > cow 11, cow 11 > cow 55, cow 22 > cow 33, cow 11 > cow 44, and cow 33 > cow 44 (where the '>' notation means "produces milk more quickly").

从输入样例中可以发现,约翰已经知道的排名有奶牛 22 >奶牛 11 >奶牛 55 和奶牛 22 >奶牛 33 >奶牛 44 ,奶牛 22 排名第一。但是他还需要知道奶牛 11 的名次是否高于奶牛 33 来确定排名第 22 的奶牛,假设奶牛 11 的名次高于奶牛 33。接着,他需要知道奶牛 44 和奶牛 55 的名次,假设奶牛 55 的名次高于奶牛 44。在此之后,他还需要知道奶牛 55 的名次是否高于奶牛 33。所以,他至少仍需要知道 33 个关于奶牛的排名。

数据规模与约定

对于 100%100\% 的数据,1n1031\le n\le 10^31m1041\le m\le 10^41x,y1031\le x,y\le 10^3

题目来源

Gold