入门⏱ 1000ms💾 256MB#P2286🏷️ 传递闭包图论

题目描述

$n$ 颗珍珠重量互不相同。给出 $m$ 次两两比较结果($x$ 比 $y$ 重)。 比较关系可传递:若 $x$ 比 $y$ 重、$y$ 比 $z$ 重,则 $x$ 比 $z$ 重。

珍珠共 $n$ 颗($n$ 为奇数),"中间珠"指重量排在第 $(n+1)/2$ 位的珍珠。 若某颗珍珠已被证明比超过 $n/2$ 颗珍珠都重,或比超过 $n/2$ 颗珍珠都轻, 则它肯定不是中间珠。统计这样的珍珠总数。

输入格式

第一行两个整数 $N, M$($N$ 为奇数,$N \le 99$); 以下 $M$ 行,每行两个整数 $x, y$,表示珍珠 $x$ 比 $y$ 重。

输出格式

一行,一个整数:肯定不是中间重量的珍珠总数。

数据范围

$$1 \le N \le 99$$
且 $N$ 为奇数

样例输入 #1
5 4
2 1
4 3
5 1
4 2
样例输出 #1
2
样例输入 #2
1 0
样例输出 #2
0