頂点・辺ともに無いグラフ \(G_0\) を考え、\(i=1,2,\ldots,N\) の順に次の操作を行うことを考えます。

• \(G_{i-1}\) に、頂点 \(i\) と、\(G\) に存在する頂点 \(i\) と頂点 \(j\) \((j\leq i)\) を結ぶ辺をすべて付け足し、それをグラフ \(G_i\) とする。

付け加える辺は、頂点 \(i\) から出る辺・入る辺および自己ループを（もう一方の頂点番号が \(i\) 以下である限り）すべて含みます。定義より \(G_N=G\) であり、\(G_i\) は問題文の操作において、\(G\) から頂点 \(i+1, i+2, \ldots, N\) をすべて取り除いたグラフとなっていることに注意してください。

このとき問題文における \(k=i\) のときに高橋君が目標を達成できることの必要十分条件は、 \(G_i\) において頂点 \(1\) から頂点 \(1,2,\ldots,i\) のすべてに到達できることであることを示します。

これが十分条件であることは明らかです。
必要条件であることについて、\(G_i\) において頂点 \(1\) から到達可能で無い頂点 \(j\) が存在したとすると、\(G\) において頂点 \(1\) を始点、頂点 \(j\) を終点とするパスであって、途中で経由する頂点の番号がすべて \(i\) 以下であるようなものは存在しません。すなわち、頂点 \(1\) から頂点 \(j\) に到達するためには番号が \(i\) より大きい頂点を経由する必要があり、このとき、どのように頂点を削除しても、頂点 \(1\) から到達できる頂点の集合に \(j\) が含まれるならば番号が \(i\) より大きい頂点もその集合に含まれています。よって、条件をみたすような操作は存在せず、これは必要条件にもなっています。

次に、\(k=i\) において高橋君が目標を達成できるとき、削除する必要のある頂点数の最小値について考えます。まず、\(G\) において、頂点番号が \(i+1\) 以上であり、頂点 \(1,2,\ldots,i\) のいずれかから直接辺が伸びている頂点は削除する必要があります。頂点 \(1,2,\ldots,i\) は絶対に削除できず、仮定からこれらは頂点 \(1\) から到達可能であるため、削除しない限り、頂点 \(1,2,\ldots,i\) のいずれかから直接辺が伸びている頂点は頂点 \(1\) から到達できてしまうからです。逆に、そのような頂点を削除したとき、頂点番号が \(i+1\) 以上の他の頂点は削除せずとも、頂点 \(1\) から到達できません。もし、頂点 \(1\) \(\rightarrow\) \(\cdots\) \(\rightarrow\) 頂点 \(j(>i)\) のようなパスが存在したとすると、このパスにおいて初めて登場する、頂点番号が \(i+1\) 以上の頂点は、仮定より削除されて存在しないはずであるためです。

よって、\(G_i\) を順に構成していき、\(G_i\) において頂点 \(1\) から到達可能な頂点の数、および \(G_i\) において頂点 \(1\) から到達可能な頂点から \(G\) の辺を高々 \(1\) 回通って到達可能な頂点の数を数え、前者が \(i\) 未満なら \(-1\) を、そうでないならば後者から前者を引いた値を出力すれば良いです。

\(G_{i-1}\) から \(G_i\) へ頂点および辺を付属したとき、新たに頂点 \(1\) から到達可能となる頂点は次の \(2\) 種類です。

• 頂点 \(j\) から頂点 \(i\) への辺が存在する頂点 \(j\) であって、\(G_{i-1}\) において頂点 \(1\) から到達可能なものが存在するとき、頂点 \(1\) から \(i\) までも到達可能である。
• 頂点 \(1\) から頂点 \(i\) まで到達可能なとき、頂点 \(i\) から、「頂点番号が \(i\) 以下かつ \(G_{i-1}\) では頂点 \(1\) から到達可能でなかった」頂点のみを通って到達できる頂点も頂点 \(1\) から到達可能となる。

これらは隣接リストなどで辺を管理し、深さ優先探索 (DFS) などを用いるで新たに到達可能となる頂点を列挙することができます。 適切に実装したとき、\(G_1,G_2,\ldots,G_N\) それぞれにおいて新たに頂点 \(1\) から到達可能となる頂点を列挙する過程で、各辺は合計で高々 \(2\) 回しか参照されないことからこの列挙にかかる時間計算量は \(O(N+M)\) となります。

なお、\(G_i\) において頂点 \(1\) から到達可能な頂点から \(G\) の辺を高々 \(1\) 回通って到達可能な頂点の数については、新たに頂点 \(1\) から到達可能となる頂点を列挙する際に、その頂点から出ている辺の先の頂点をすべて確認することで数えることができ、こちらについても全体で \(O(N+M)\) で行うことができます。
また、こちらについては、代わりに「頂点 \(1,2,\ldots,i\) のうち \(1\) つ以上から \(G\) の辺を高々 \(1\) 回通って到達可能な頂点」の数を数えても答えは変わらず、この場合は各頂点 \(v\) について、頂点 \(v\) 自身あるいは頂点 \(v\) から辺が伸びている頂点 \(u\) であって、その頂点 へ辺が伸びている頂点および自身のうち最も番号が小さいものが頂点 \(v\) であるようなものの数を数え、これらの累積和を取ることによって求めることができます。この場合も時間計算量は \(O(N+M)\) となります。

よって、\(k=1,2,\ldots,N\) それぞれの場合について、高橋君が目標を達成できるかの判定および、達成できる場合に削除する必要のある頂点数の最小値の求値を全体で \(O(N+M)\) で行うことができます。
よって、この問題を解くことができました。

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;
}