← 返回题目列表

AtCoder · abc292_e

H. 传递性

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个简单的有向图 N 顶点编号 1 to N 和 M 边编号 1 to 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
  • (u_i,v_i) \neq (u_j,v_j) if i \neq j.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
u_1 v_1
\vdots
u_M v_M

输出

打印答案。


示例输入 1

4 3
2 4
3 1
4 3

示例输出 1

3

最初,条件不满足,因为例如对于顶点 2, 4,和 3,有来自顶点的有向边 2 到顶点 4 并从顶点 4 到顶点 3,但不是来自顶点 2 到顶点 3.

您可以通过添加以下三个有向边来使图形满足条件:

  • 顶点一 2 到顶点 3,
  • 顶点一 2 到顶点 1,和
  • 顶点一 4 到顶点 1.

另一方面,通过添加两条或更少的边无法满足条件,因此答案是 3.


示例输入 2

292 0

示例输出 2

0

示例输入 3

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

示例输出 3

12