/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純有向グラフが与えられます。辺 i は頂点 u_i から頂点 v_i への有向辺です。
また、あなたは次の操作を 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
初め、一例として頂点 2,4,3 について、頂点 2 から頂点 4 への有向辺と頂点 4 から頂点 3 への有向辺がともに存在するにもかかわらず、頂点 2 から頂点 3 への有向辺は存在せず、条件を満たさない状態です。
そこで、以下の 3 本の有向辺を追加すると条件を満たす状態になります。
- 頂点 2 から頂点 3 への有向辺
- 頂点 2 から頂点 1 への有向辺
- 頂点 4 から頂点 1 への有向辺
一方、3 本未満の追加で条件を満たす状態には出来ないため、答えは 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
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