Union Find を活用すれば，公式解説よりさらに簡潔に実装できます．

公式解説での判定問題・最小化問題は以下のように解けます．

• 判定問題： \(\max(u,v)\leq k\) である辺 \((u,v)\) のみからなる部分グラフ上で頂点 \(1\) を含む連結成分の大きさが \(k\) であるか．
• 最小化問題： 求める値は \((\min(u,v)\leq k\) である辺 \((u,v)\) のみからなる部分グラフ上で頂点 \(1\) を含む連結成分の大きさ\()-k\)．

ある頂点を含む連結成分の大きさは ACL の dsu では size によって取得できます．（参考：ACL Document - DSU）

提出(C++) ，提出(PyPy)

実装例(C++)

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

int main() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<int>> edges(n);
	while (m--) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	
	atcoder::dsu uf_small(n), uf_large(n);
	
	for (int i = 0; i < n; i++) {
		for (auto j : edges[i]) (j < i ? uf_small : uf_large).merge(i, j);
		cout << (uf_small.size(i) == i + 1 ? uf_large.size(i) - (i + 1) : -1) << "\n";
	}
}