题目描述

给定一个简单有向图，有 $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$

输出

输出答案。

示例输入 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