Contest Duration: - (local time) (100 minutes) Back to Home
E - Transitivity /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

また、あなたは次の操作を 0 回以上何度でも行えます。

• 相異なる頂点 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


そこで、以下の 3 本の有向辺を追加すると条件を満たす状態になります。

• 頂点 2 から頂点 3 への有向辺
• 頂点 2 から頂点 1 への有向辺
• 頂点 4 から頂点 1 への有向辺

### 入力例 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


Score : 500 points

### 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