[Usaco2008 Jan]Cow Contest奶牛的比赛
农夫约翰的 头奶牛参加了一场程序设计竞赛。奶牛依次编号为 到 ,每头奶牛的编程能力各不相同,因此它们之间存在唯一且明确的能力排名。
比赛分为若干轮,每轮由两头指定编号的奶牛进行对决。如果编号为 的奶牛编程能力强于编号为 的奶牛,那么在它们的对决中,编号为 的奶牛一定会获胜。
农夫约翰收集了全部 轮比赛的结果,希望根据这些信息推断出尽可能多的奶牛的确切排名。所有比赛结果保证不会相互矛盾。
输入格式
第一行包含两个以空格分隔的整数 和 ,分别表示奶牛数量和比赛轮数。
接下来 行,每行包含两个以空格分隔的整数 和 ,表示编号为 的奶牛在该轮比赛中战胜了编号为 的奶牛。
输出格式
输出一个整数,表示能够确定确切排名的奶牛数量。
样例输入
5 5
4 3
4 2
3 2
1 2
2 5
样例输出
2
数据范围
- ;
- ;
- ,,且 ;
- 比赛结果保证不会自相矛盾。
来源与许可
本题为 USACO 2008 January 试题「Cow Contest」,题面与测试数据整理自 BZOJ。
样例 1
输入
5 5
4 3
4 2
3 2
1 2
2 5
输出
2