传递性

题目描述

给定一个简单有向图,它有 $N$ 个顶点(编号 $1$ 到 $N$)和 $M$ 条边(编号 $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$

输出格式

输出答案。

样例

4 3
2 4
3 1
4 3

3

初始时条件不满足,例如对于顶点 $2$、$4$、$3$,存在从顶点 $2$ 到顶点 $4$ 和从顶点 $4$ 到顶点 $3$ 的有向边,但不存在从顶点 $2$ 到顶点 $3$ 的有向边。

添加以下三条有向边即可使图满足条件:

从顶点 $2$ 到顶点 $3$,

从顶点 $2$ 到顶点 $1$,

从顶点 $4$ 到顶点 $1$。

另一方面,添加两条或更少的有向边无法满足条件,因此答案为 $3$。

292 0

0

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

12

数据范围

• $3 \le N \le 2000$
• $0 \le M \le 2000$
• $1 \le u_i, v_i \le N$
• $u_i \ne v_i$
• 当 $i \ne j$ 时,$(u_i,v_i) \ne (u_j,v_j)$
• 输入中的所有值均为整数