比赛场次 426
比赛名称 20181002
比赛状态 已结束比赛成绩
开始时间 2018-10-02 08:30:00
结束时间 2018-10-02 12:00:00
开放分组 全部用户
注释介绍 国庆七天乐2
题目名称 奶牛的比赛
输入输出 contest.in/out
时间限制 1000 ms (1 s)
内存限制 16 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar雾茗 AAAAAAAAAA 0.011 s 0.35 MiB 100
Gravatar666666666666 AAAAAAAAAA 0.013 s 0.36 MiB 100
Gravatarpztl AAAAAAAAAA 0.014 s 0.33 MiB 100
Gravatar梦那边的美好ET AAAAAAAAAA 0.016 s 0.41 MiB 100
Gravatar观、一世沧桑如画 AAAAAAAAAA 0.025 s 0.33 MiB 100

奶牛的比赛

★★   输入文件:contest.in   输出文件:contest.out   简单对比
时间限制:1 s   内存限制:16 MiB

【题目描述】

  $FJ$的$N(1 <= N <= 100)$头奶牛们最近参加了场程序设计竞赛:)。在赛场上,奶牛们按$1..N$依次编号。每头奶牛的编程能力不尽相同,并且没有哪两头奶牛的水平不相上下,也就是说,奶牛们的编程能力有明确的排名。

  整个比赛被分成了若干轮,每一轮是两头指定编号的奶牛的对决。如果编号为$A$的奶牛的编程能力强于编号为$B$的奶牛$(1 <= A <= N; 1 <= B <= N; A != B)$,那么她们的对决中,编号为$A$的奶牛总是能胜出。

  $FJ$想知道奶牛们编程能力的具体排名,于是他找来了奶牛们所有$M(1 <= M <= 4,500)$轮比赛的结果,希望你能根据这些信息,推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

【输入格式】

第$1$行: $2$个用空格隔开的整数:$N$ 和 $M$;

第$2$..$M+1$行: 每行为$2$个用空格隔开的整数$A$、$B$,描述了参加某一轮比赛的奶牛的编号,以及结果(编号为$A$,即为每行的第一个数的奶牛为胜者);

【输出格式】

第$1$行: 输出$1$个整数,表示排名可以确定的奶牛的数目;

【样例输入】

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

【样例输出】

2

【提示】

编号为$2$的奶牛输给了编号为$1$、$3$、$4$的奶牛,也就是说她的水平比这$3$头奶牛都差。而编号为$5$的奶牛又输在了她的手下,也就是说,她的水平比编号为$5$的奶牛强一些。于是,编号为$2$的奶牛的排名必然为第$4$,编号为$5$的奶牛的水平必然最差。其他$3$头奶牛的排名仍无法确定。

【来源】

$USACO$