CF687E.TOF

Today Pari gave Arya a cool graph problem. Arya wrote a non-optimal solution for it, because he believes in his ability to optimize non-optimal solutions. In addition to being non-optimal, his code was buggy and he tried a lot to optimize it, so the code also became dirty! He keeps getting Time Limit Exceeds and he is disappointed. Suddenly a bright idea came to his mind!

Here is how his dirty code looks like:

dfs(v)
{
set count[v] = count[v] + 1
if(count[v] < 1000)
{
foreach u in neighbors[v]
{
if(visited[u] is equal to false)
{
dfs(u)
}
break
}
}
set visited[v] = true
}

main()
{
input the digraph()
TOF()
foreach 1<=i<=n
{
set count[i] = 0 , visited[i] = false
}
foreach 1 <= v <= n
{
if(visited[v] is equal to false)
{
dfs(v)
}
}
... // And do something cool and magical but we can't tell you what!
}

He asks you to write the TOF function in order to optimize the running time of the code with minimizing the number of calls of the dfs function. The input is a directed graph and in the TOF function you have to rearrange the edges of the graph in the list neighbors for each vertex. The number of calls of dfs function depends on the arrangement of neighbors of each vertex.

今天帕里给阿莉亚出了一道很酷的图论题目。阿莉亚为此写了一个非最优解，因为她坚信自己有能力将非最优解优化。然而，该代码不仅非最优，还存在 bug；而且她为优化这段代码付出了大量努力，结果代码也变得十分混乱！她一直遭遇“超时”（Time Limit Exceed），感到非常沮丧。突然，一个绝妙的想法闪现在她脑海中！

以下是她那混乱不堪的代码：

dfs(v)  
{  
 set count[v] = count[v] + 1  
 if(count[v] < 1000)  
 {  
 foreach u in neighbors[v]  
 {  
 if(visited[u] is equal to false)  
 {  
 dfs(u)  
 }  
 break  
 }  
 }  
 set visited[v] = true  
}  
  
main()  
{  
 input the digraph()  
 TOF()  
 foreach 1<=i<=n  
 {  
 set count[i] = 0 , visited[i] = false  
 }  
 foreach 1 <= v <= n  
 {  
 if(visited[v] is equal to false)  
 {  
 dfs(v)  
 }  
 }  
 ... // 接下来会执行一些酷炫而神奇的操作，但此处我们不能透露具体内容！  
}  

她请你编写 TOF 函数，以通过最小化 dfs 函数的调用次数来优化整个程序的运行时间。输入是一个有向图，在 TOF 函数中，你需对每个顶点 v 的邻接表 neighbors[v] 中的边进行重排。dfs 函数被调用的总次数取决于每个顶点邻接表中邻居节点的排列顺序。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 5000) — the number of vertices and then number of directed edges in the input graph.

Each of the next m lines contains a pair of integers u__i and v__i (1  ≤  u__i,  v__i  ≤  n), meaning there is a directed edge in the input graph.

You may assume that the graph won't contain any self-loops and there is at most one edge between any unordered pair of vertices.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 5000$）—— 分别表示输入图中的顶点数和有向边数。

接下来的 $m$ 行中，每行包含一对整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示输入图中存在一条从 $u_i$ 指向 $v_i$ 的有向 边。

你可以假设该图不包含任何自环，且任意无序顶点对之间至多只有一条边。

Print a single integer — the minimum possible number of dfs calls that can be achieved with permuting the edges.

输出一个整数——通过重新排列边所能达到的最小 DFS 调用次数。