P0831

[Usaco2008 Jan]Cow Contest奶牛的比赛

[Usaco2008 Jan]Cow Contest奶牛的比赛

农夫约翰的 NN 头奶牛参加了一场程序设计竞赛。奶牛依次编号为 11 到 NN,每头奶牛的编程能力各不相同,因此它们之间存在唯一且明确的能力排名。

比赛分为若干轮,每轮由两头指定编号的奶牛进行对决。如果编号为 AA 的奶牛编程能力强于编号为 BB 的奶牛,那么在它们的对决中,编号为 AA 的奶牛一定会获胜。

农夫约翰收集了全部 MM 轮比赛的结果,希望根据这些信息推断出尽可能多的奶牛的确切排名。所有比赛结果保证不会相互矛盾。

输入格式

第一行包含两个以空格分隔的整数 NN 和 MM,分别表示奶牛数量和比赛轮数。

接下来 MM 行,每行包含两个以空格分隔的整数 AA 和 BB,表示编号为 AA 的奶牛在该轮比赛中战胜了编号为 BB 的奶牛。

输出格式

输出一个整数,表示能够确定确切排名的奶牛数量。

样例输入

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

样例输出

2

数据范围

  • 1≤N≤1001\le N\le 100;
  • 1≤M≤45001\le M\le 4500;
  • 1≤A≤N1\le A\le N,1≤B≤N1\le B\le N,且 A≠BA\ne B;
  • 比赛结果保证不会自相矛盾。

来源与许可

本题为 USACO 2008 January 试题「Cow Contest」,题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

2