当前没有测试数据。

E - 传递性

分数：$500$ 分

问题描述

给定一个简单有向图，有 $N$ 个从 $1$ 到 $N$ 编号的顶点和 $M$ 条从 $1$ 到 $M$ 编号的边。第 $i$ 条边是从顶点 $u_i$ 到顶点 $v_i$ 的有向边。

您可以执行以下操作零次或多次。

• 选择不同的顶点 $x$ 和 $y$，使得从顶点 $x$ 到顶点 $y$ 没有有向边，并且从顶点 $x$ 到顶点 $y$ 添加一条有向边。

找到使得图满足以下条件所需的最少操作次数：

• 对于任意三个不同的顶点 $a$、$b$ 和 $c$，如果从顶点 $a$ 到顶点 $b$ 和从顶点 $b$ 到顶点 $c$ 有有向边，那么从顶点 $a$ 到顶点 $c$ 也有有向边。

约束

• $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)$。
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$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