The optimal strategy is to repeatedly find distinct vertices \(a\), \(b\) and \(c\) such that a directed edge from vertex \(a\) to vertex \(b\) and another from vertex \(b\) to vertex \(c\) exist but one from vertex \(a\) to vertex \(c\) doesn’t, and add a directed edge from vertex \(a\) to vertex \(c\); however, it is a bit difficult to finish it within the execution time limit.

In fact, a directed edge from vertex \(x\) exists in the final graph if and only if it goes to a vertex reachable from vertex \(x\) in the original graph (except for \(x\) itself).

Therefore, it is sufficient to count the reachable vertices from each vertex in the original graph with BFS (Breadth-First Search) or DFS (Depth-First Search). Since one can perform BFS or DFS from a vertex in an \(\mathrm{O}(M)\) time, the total complexity is \(\mathrm{O}(NM)\).

Sample code (C++, with BFS)

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N,M;
	cin>>N>>M;
	vector<vector<int>> E(N);
	
	for(int i=0;i<M;i++){
		int u,v;
		cin>>u>>v;
		E[u-1].push_back(v-1);
	}
	
	int ans = 0;
	
	for(int i=0;i<N;i++){
		vector<bool> f(N,false);
		f[i] = true;
		queue<int> Q;
		Q.push(i);
		
		while(Q.size()>0){
			int x = Q.front();
			Q.pop();
			for(int j=0;j<E[x].size();j++){
				int y = E[x][j];
				if(f[y])continue;
				f[y] = true;
				Q.push(y);
				ans++;
			}
		}
	}
	
	ans -= M;
	cout<<ans<<endl;
	
	return 0;
}