[USACO08JAN] Cow Contest S

题目描述

$ N (1 ≤ N ≤ 100) $ cows, conveniently numbered $ 1 ~ N $ , are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors. The contest is conducted in several head-to-head rounds, each between two cows. If cow $ A $ has a greater skill level than cow $ B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) $, then cow $ A $ will always beat cow $ B $ . Farmer John is trying to rank the cows by skill level. Given a list the results of $ M (1 ≤ M ≤ 4,500) $ two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory. FJ的 $N$($1 \leq N \leq 100$)头奶牛们最近参加了场程序设计竞赛。在赛场上,奶牛们按 $1, 2, \cdots, N$ 依次编号。每头奶牛的编程能力不尽相同,并且没有哪两头奶牛的水平不相上下,也就是说,奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮,每一轮是两头指定编号的奶牛的对决。如果编号为 $A$ 的奶牛的编程能力强于编号为 $B$ 的奶牛 ($1 \leq A, B \leq N$,$A \neq B$),那么她们的对决中,编号为 $A$ 的奶牛总是能胜出。 FJ 想知道奶牛们编程能力的具体排名,于是他找来了奶牛们所有 $M$($1 \leq M \leq 4,500$)轮比赛的结果,希望你能根据这些信息,推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

输入输出格式

输入格式


第一行两个用空格隔开的整数 $N, M$。 第 $2\sim M + 1$ 行,每行为两个用空格隔开的整数 $A, B$ ,描述了参加某一轮比赛的奶牛的编号,以及结果(每行的第一个数的奶牛为**胜者**)。

输出格式


输出一行一个整数,表示排名可以确定的奶牛的数目。

输入输出样例

输入样例 #1

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

输出样例 #1

2

说明

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