题目描述

农夫约翰有 $n$ 头奶牛，每一头奶牛都有一个确定的独一无二的正整数产奶率。约翰想要让这些奶牛按产奶率从高到低排序。 约翰已经比较了 $m$ 对奶牛的产奶率，但他发现，他还需要再做一张关于另外 $c$ 对奶牛的产奶率比较，才能推断出所有奶牛的产奶率排序。请帮他确定 $c$ 的最小值。

输入格式

第一行包含两个用空格分开的整数 $n$ 和 $m$。
接下来 $m$ 行，每行有两个用空格分开的整数 $m$ 和 $y$，表示奶牛 $x$ 的产奶率高于奶牛 $y$。

输出格式

$c$ 的最小值。

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

3

样例说明

FJ is comparing $5$ cows and has already determined that cow $2$ > cow $1$, cow $1$ > cow $5$, cow $2$ > cow $3$, cow $1$ > cow $4$, and cow $3$ > cow $4$ (where the '>' notation means "produces milk more quickly").

从输入样例中可以发现，约翰已经知道的排名有奶牛 $2$ >奶牛 $1$ >奶牛 $5$ 和奶牛 $2$ >奶牛 $3$ >奶牛 $4$ ，奶牛 $2$ 排名第一。但是他还需要知道奶牛 $1$ 的名次是否高于奶牛 $3$ 来确定排名第 $2$ 的奶牛，假设奶牛 $1$ 的名次高于奶牛 $3$。接着，他需要知道奶牛 $4$ 和奶牛 $5$ 的名次，假设奶牛 $5$ 的名次高于奶牛 $4$。在此之后，他还需要知道奶牛 $5$ 的名次是否高于奶牛 $3$。所以，他至少仍需要知道 $3$ 个关于奶牛的排名。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^3$，$1\le m\le 10^4$，$1\le x,y\le 10^3$。

题目来源

Gold