Consider repeatedly performing the following operation of writing integers on vertices of graph \(G\) given in the input as many times as possible. Initially, no vertex has an integer written on it.

In the \(i\)-th operation, find “a vertex of \(G\) such that no integer is yet written on it, and it has no outgoing edges or every vertices pointed by its outgoing edges has an integer written on it.” If such a vertex exists, write \(i\) on it; if not, terminate the sequence of operations without performing the \((i+1)\)-th operation.

The sequence of operations terminates after at most \(N\) operations.

When it is terminated, by the conditions of writing integers, every vertex with an integer written on it has no outgoing edges, or every destination of its outgoing edges has a smaller integer. Thus, no matter which edge he chooses, he will reach another vertex with a strictly smaller integer written on it. Therefore, from a vertex with \(i\) written on it, Takahashi can travel at most \((i-1)\) times. Thus, he can only move finite number of times.

Conversely, consider the other vertices. From a vertex \(v\) without an integer, there is at least one outgoing edge pointing at another vertex without an integer. Let \(f(v)\) be the next vertex of \(v\) determined by this claim. If there are multiple such vertices, choose arbitrarily.

Denoting by \(f^k\) the \(k\)-th composition of \(f\), each of \(v=f^0(v)\), \(f(v)\), \(f(f(v))\), \(\ldots\), \(f^k(v)\), \(\ldots\) is a vertex without an integer written on it, and for each \(k\geq 0\), there is an edge from \(f^k(v)\) to \(f^{k+1}(v)\). Therefore, he can repeat travelling from vertex \(v\) as many as he wants.

Hence, the desired value is the number of vertex on which no integer was written as a result of the procedure above.

If you implement it naively, it will cost \(O(NM)\) time, which will not finish in the time limit. Here, note that once a vertex satisfied the condition for an integer to be written, the vertex never becomes invalid until an integer is actually written. So consider repeating putting the vertices that satisfied the condition to a queue, popping vertices as much as possible from the queue, and writing integers on them.

Before the first operation, the vertices that satisfy the condition are those without outgoing edges, which can be found in an \(O(N)\) time (or \(O(N+M)\) if recording the information of edges is taken into account) by checking the outdegree of each vertex. Moreover, the vertices that do not satisfy the condition before the \(i\)-th operation and do satisfy the condition before the \((i+1)\)-th operation for the first time are limited to the starting vertices of the edges pointed at that vertex. Therefore, it is sufficient to check them before the \((i+1)\)-th operation. Here, the check on whether each vertex satisfies the condition of outdegrees is done at most \(M\) times in total in the \(N\) operations, so it can be done in a total of \(O(M)\) time.

Therefore, the problem has been solved in a total of \(O(N+M)\) time.

When implementing the solution above, it is easier to reverse the edges.

Sample code in C++ ;

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

int main(void) {
	int n, m;
	cin >> n >> m;

	vector<vector<int> > e(n);
	vector<int> out(n, 0);
	int x, y, sz, cur;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		e[y - 1].push_back(x - 1);
		out[x - 1]++;
	}

	queue<int>que;
	int ans = n;

	for (int i = 0; i < n; i++)if (out[i] == 0)que.push(i);
	while (!que.empty()) {
		ans--;
		cur = que.front();
		que.pop();
		sz = e[cur].size();
		for (int i = 0; i < sz; i++) {
			out[e[cur][i]]--;
			if (out[e[cur][i]] == 0)que.push(e[cur][i]);
		}
	}
	cout << ans << endl;
	return 0;
}