Consider a graph \(G_0\) with no vertices nor edges, and performing the following operation for \(i=1,2,\ldots,N\):

• Let graph \(G_i\) be the graph obtained by adding to \(G_{i-1}\) vertex \(i\) and all the edges in \(G\) connecting vertices \(i\) and \(j\) \((j\leq i)\).

The edges to add include all edges going to and from vertex \(i\), and the self loops (as long as the other end’s vertex number is \(i\) or less). Note that by definition \(G_N=G\), and \(G_i\) is the graph obtained by removing vertices \((i+1),(i+2),\ldots,N\) from \(G\) as in the operation in the problem statement.

Then, Takahashi can achieve the goal when \(k=i\) in the problem statement if and only if vertices \(1,2,\ldots,i\) are all reachable from vertex \(1\) in graph \(G_i\).

It is obvious that this is a sufficient condition. To show the necessity, suppose that \(G_i\) has a vertex \(j\) that is not reachable from vertex \(1\). Then there is no path that starts from vertex \(1\), ends at vertex \(j\), and passes through only vertices with numbers \(i\) or less. Thus, to reach to vertex \(j\) from vertex \(1\), we need to pass through a vertex with number greater than \(i\); in this case, no matter how you remove vertices, if the set of vertices reachable from vertex \(1\) contains \(j\), then the set will also contain a vertex with vertex number greater than \(i\). Thus, no operation satisfies the condition, so the condition is a necessary condition.

Next, when Takahashi can achieve the goal for \(k=i\), consider the minimum number of vertices that need to be removed. First, we need to remove vertices with numbers \((i+1)\) or greater, that are directly connected with an edge to any of vertices \(1,2,\ldots,i\). This is because, since vertices \(1,2,\ldots,i\) can never be removed, and these are reachable by assumption, if there is a vertex that is directly connected to any of \(1,2,\ldots,i\) with an edge, then that vertex also becomes reachable. Conversely, when all such vertices are removed, any vertex with numbers \((i+1)\) or greater becomes unreachable. This is because, if there exists a path like vertex \(1\) \(\rightarrow\) \(\cdots\) \(\rightarrow\) vertex \(j (>i)\), then the vertex with numbers \((i+1)\) or greater that occurs for the first time in this path should be removed by assumption.

Therefore, it is sufficient to construct \(G_i\) in order, manage the number of vertices reachable from vertex \(1\) in \(G_i\), and vertices reachable via an edge in \(G\) from a vertex reachable from vertex \(1\) in \(G_i\), and print \(-1\) if the former is less than \(-1\), and the result of subtracting the latter from the former otherwise.

When we add vertices and edges to turn \(G_{i-1}\) into \(G_i\), the following two kinds of vertices may be come newly reachable from vertex \(1\):

• If there exists an edge from vertex \(j\) to vertex \(i\) that are reachable from vertex \(i\) in graph \(G_{i-1}\), then it is reachable from vertex \(1\) to vertex \(i\).
• If it is reachable from vertex \(1\) to vertex \(i\), then any vertices that are reachable from vertex \(i\) via “the vertices with numbers \(i\) or less that were not reachable from vertex \(1\) in \(G_{i-1}\).”

By managing the edges in an adjacency list, the newly reachable vertices can be enumerated with an algorithm like DFS (Depth-First Search). With an appropriate implementation, this enumeration costs a total of \(O(N+M)\) time, because each edge is referenced at most twice during the enumerations of newly reachable vertices when processing \(G_1,G_2,\ldots,G_N\).

Note that the number of vertices reachable, from a vertex reachable from vertex \(1\) in \(G_i\), via at most one edge of \(G\), can be counted when enumerating the newly reachable vertices from vertex \(1\), by inspecting all vertices directly connected via an edge connected to vertex, which can also be processed in \(O(N+M)\) time.
As for this part, we may count the number of “vertices that are reachable, from at least one of vertices \(1,2,\ldots,i\), via at most one edge of \(G\)” instead. This approach can be implemented by counting, for each vertex \(v\), the number of vertices \(u\) that are vertex \(v\) itself or a directly adjacent to vertex \(v\), such that vertex \(v\) has the smallest vertex number among the vertices directly adjacent to vertex \(v\) and that vertex itself, and taking the cumulative sum of that counts. This approach also costs \(O(N+M)\).

Therefore, one can determine if Takahashi can achieve the goal and how many vertices need to be removed at minimum, for \(k=1,2,\ldots,N\) in a total of \(O(N+M)\) time.
Thus, the problem has been solved.

Sample code (C++):

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

#define N (int)3e+5

vector<int>e[N];
bool vis[N];
bool can[N];
int cvis,ccan;

void dfs(int k,int mx){
	vis[k]=true;
	cvis++;
	int sz=e[k].size();
	for(int i=0;i<sz;i++){
		if((!vis[e[k][i]])&&(e[k][i]<=mx))dfs(e[k][i],mx);
		if(!can[e[k][i]]){
			can[e[k][i]]=true;
			ccan++;
		}
	}
	return;
}

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

	for(int i=0;i<n;i++){
		vis[i]=false,can[i]=false;
	}
	cvis=0,ccan=0;
	
	for(int i=0;i<n;i++){
		if(i==0){
			can[0]=true;
			ccan++;
		}
		if(can[i])dfs(i,i);
		if(cvis==(i+1))cout<<(ccan-cvis)<<endl;
		else cout<<-1<<endl;
	}

	return 0;
}