102924: [Atcoder]ABC292 E - Transitivity

Problem Statement

You are given a simple directed graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ is a directed edge from vertex $u_i$ to vertex $v_i$.

You may perform the following operation zero or more times.

• Choose distinct vertices $x$ and $y$ such that there is no directed edge from vertex $x$ to vertex $y$, and add a directed edge from vertex $x$ to vertex $y$.

Find the minimum number of times you need to perform the operation to make the graph satisfy the following condition.

• For every triple of distinct vertices $a$, $b$, and $c$, if there are directed edges from vertex $a$ to vertex $b$ and from vertex $b$ to vertex $c$, there is also a directed edge from vertex $a$ to vertex $c$.

Constraints

• $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$.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$

Output

Print the answer.

Sample Input 1

4 3
2 4
3 1
4 3

Sample Output 1

3

Initially, the condition is not satisfied because, for instance, for vertices $2$, $4$, and $3$, there are directed edges from vertex $2$ to vertex $4$ and from vertex $4$ to vertex $3$, but not from vertex $2$ to vertex $3$.

You can make the graph satisfy the condition by adding the following three directed edges:

• one from vertex $2$ to vertex $3$,
• one from vertex $2$ to vertex $1$, and
• one from vertex $4$ to vertex $1$.

On the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is $3$.

Sample Input 2

292 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

12

问题描述

给你一个有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的有向边。

约束

• 3≤N≤2000
• 0≤M≤2000
• 1≤u_i ,v_i≤N
• u_i≠v_i
• (u_i,v_i)≠(u_j,v_j)如果i≠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