AT_abc292_e [ABC292E] Transitivity

给定一个有 $N$ 个顶点、$M$ 条边的简单有向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边是从顶点 $u_i$ 指向顶点 $v_i$ 的有向边。 你可以进行如下操作，操作次数不限（可以为 $0$ 次）： - 选择两个不同的顶点 $x, y$，且当前不存在从 $x$ 到 $y$ 的有向边，然后添加一条从 $x$ 到 $y$ 的有向边。 请你求出，最少需要进行多少次操作，才能使得图满足以下条件： - 对于任意不同的顶点 $a, b, c$，如果存在从 $a$ 到 $b$ 的有向边，且存在从 $b$ 到 $c$ 的有向边，那么必须存在从 $a$ 到 $c$ 的有向边。

输入按以下格式从标准输入给出。 > $N$ $M$ > $u_1$ $v_1$ > $\vdots$ > $u_M$ $v_M$

输出答案。

## 限制条件 - $3 \leq N \leq 2000$ - $0 \leq M \leq 2000$ - $1 \leq u_i, v_i \leq N$ - $u_i \neq v_i$ - 如果 $i \neq j$，则 $(u_i, v_i) \neq (u_j, v_j)$ - 所有输入均为整数 ## 样例解释 1 初始时，例如对于顶点 $2, 4, 3$，虽然存在从顶点 $2$ 到顶点 $4$ 的有向边和从顶点 $4$ 到顶点 $3$ 的有向边，但不存在从顶点 $2$ 到顶点 $3$ 的有向边，因此不满足条件。此时，添加如下 $3$ 条有向边后即可满足条件： - 从顶点 $2$ 到顶点 $3$ 的有向边 - 从顶点 $2$ 到顶点 $1$ 的有向边 - 从顶点 $4$ 到顶点 $1$ 的有向边 另一方面，若少于 $3$ 条边则无法满足条件，因此答案为 $3$。 由 ChatGPT 4.1 翻译