Initially, we build a graph where the nodes represent towns and edges represent the direction of required trips between two towns.

Now we view this graph as an undirected graph. Clearly, the graph has at least 1 connected component.

Then, we separate the original graph into its connected components (i.e no edges exist between components). Some possible ways to do this are DFS and DSU.

Now that we have disjoint components of the graph, we "restore" the direction of the graph's edges (i.e. view it as a directed graph again).

For each component, clearly, it either has cycle(s) or it is a DAG.

If a component has a cycle among some of its nodes (and assuming it has K nodes), we can easily include all nodes into the cycle by doing 1 -> 2 -> ... -> K -> 1. So we need to add K edges, for each of these components, to the answer.

If a component is a DAG (and assuming it has K nodes), the last node in the topological sort order of the component doesn't need to navigate anywhere else. So we only add K — 1 edges, for each of these components, to the answer.

Hence the final answer is #Towns — #DAGs.

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
int n, m, a, b, ans, par[maxn];
vector<int> to[maxn];
bool has[maxn], vis[maxn];
unordered_set<int> path;

int find(int u) {
	return par[u] == u ? u : par[u] = find(par[u]);
}

void dfs(int u) {
	vis[u] = 1;
	path.insert(u);
	for(int i = 0; i < (int) to[u].size(); i++) {
		int v = to[u][i];
		if(find(u) != find(v)) {
			continue;
		}
		if(vis[v] && path.find(v) != path.end()) {
			has[find(v)] = 1;
		}
		if(!vis[v]) {
			dfs(v);
		}
	}
	path.erase(u);
}

void addEdge(int u, int v) {
	to[u].push_back(v);
	par[find(u)] = find(v);
}

int main() {
	scanf("%d %d", &n, &m);

	ans = n;

	for(int i = 0; i < n; i++) {
		par[i] = i;
	}
	for(int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		addEdge(a, b);
	}
	for(int i = 0; i < n; i++) {
		int r = find(i);
		if(has[r]) {
			vis[i] = 1;
		}
		if(!vis[i]) {
			dfs(i);
		}
	}
	for(int i = 0; i < n; i++) {
		int r = find(i);
		if(vis[i] && !has[r]) {
			has[r] = 1;
			ans--;
		}
	}
	printf("%d\n", ans);
}