比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
雾茗 | AAAAAAAAAA | 0.011 s | 0.35 MiB | 100 |
666666666666 | AAAAAAAAAA | 0.013 s | 0.36 MiB | 100 |
pztl | AAAAAAAAAA | 0.014 s | 0.33 MiB | 100 |
梦那边的美好ET | AAAAAAAAAA | 0.016 s | 0.41 MiB | 100 |
观、一世沧桑如画 | AAAAAAAAAA | 0.025 s | 0.33 MiB | 100 |
$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$