Untitled

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

using ll = long long;

// Time Complexity: O((n + m) log n)
// Memory Complexity: O(n + m)

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	int n, m; cin >> n >> m;
	vector<vector<int>> adj(n);
	for(int i = 0; i < m; i++) {
		int u, v; cin >> u >> v; u--; v--;
		if(u == v) continue;
		adj[u].push_back(v);
	}

	set<int> cur, neigh;
	cur.insert(0);
	for(auto v : adj[0]) neigh.insert(v);
	cout << neigh.size() << "\n";

	for(int i = 1; i < n; i++) {
		// try to add i
		stack<int> st; st.push(i);
		while(!st.empty()) {
			int x = st.top(); st.pop();
			if(!neigh.count(x)) continue;
			neigh.erase(x);
			cur.insert(x);
			for(auto &y : adj[x]) {
				if(cur.count(y)) continue;
				neigh.insert(y);
				if(y <= i) st.push(y);
			}
		}
		if((int)cur.size() != i + 1) cout << "-1\n";
		else cout << neigh.size() << "\n";
	}

	return 0;
}