分数: 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