P2881 [USACO07MAR] Ranking the Cows G

题目描述

FJ 想按照奶牛产奶的能力给她们排序。现在已知有 $N$ 头奶牛（$1\le N\le {10}^3$）。FJ 通过比较，已经知道了 $M$（$1 \le M \le {10}^4$）对相对关系。每一对关系表示为 X Y，意指奶牛 $X$ 的产奶能力强于 $Y$。FJ 可以选择若干对奶牛同时询问它们的产奶量关系， 现在 FJ 想要知道，他至少还要知道多少对关系才能完成整个排序。

输入格式

第一行，两个正整数 $N$ 和 $M$。

以下 $M$ 行，每行两个正整数 $X$ 和 $Y$，表示第 $X$ 只奶牛的产奶能力强于第 $Y$ 只。

输出格式

只输出一行，一个非负整数，表示至少还需要知道的关系对数。特别地，如果 FJ 已经可以知道所有奶牛的产奶能力排序，输出0。

输入输出样例 #1

输入 #1

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

输出 #1

3

说明/提示

样例 解释

我们用 $C_i$ 表示第 $i$ 头奶牛的产奶能力。

根据给出的 $5$ 组关系，FJ 已经能知道 $C_2 > C_1 > C_5$ 且 $C_2 > C_3 > C_4$，因此第 $2$ 只奶牛的产奶能力最高。接着 FJ 需要知道 $C_1$ 和 $C_3$ 的大小关系才能知道哪只奶牛的产奶能力第二高。FJ 还需要知道 $C_4$ 和 $C_5$ 的大小关系和 $C_5$ 和 $C_3$ 的关系才能完全确定顺序。可以证明没有询问次数比 $3$ 次更少的方案了。