1. 判定問題を解く

まず、ある \(k\) に対して条件を満たすことができるか判定する方法を考えます。

もし、頂点 \(1\) から頂点 \(i\ (1\lt i\leq k)\) へ向かうのに番号が \(k\) より大きい頂点を使う必要があるなら、条件を達成することはできません。 この条件は、「番号が \(k\) より大きい頂点をすべて削除したときに頂点 \(1\) と頂点 \(i\) が異なる連結成分にあるか」と同値です。

逆に、番号が \(k\) より大きい頂点をすべて削除したとき、残る連結成分がただ \(1\) つであれば、条件を達成することができます。

この条件は、union-find などを利用して判定することができます。

これをすべての \(k\) について判定する方法を考えます。

union-find に追加する辺の順番を「辺が結ぶ \(2\) つの頂点の番号のうち大きいほう」の昇順とし、それぞれの \(k\) について適切なタイミングで判定を行うことができます。

2. 最小化問題を解く

次に、条件を満たすことができるときの消すべき頂点の個数を求めることを考えます。

\(k\) 以下の頂点と隣接している頂点はすべて削除しなければなりません。 逆に、そうでない頂点は残しても構いません。

これは、「辺が結ぶ \(2\) つの頂点の番号のうち小さいほう」の昇順で辺を処理し、結ばれている番号がより大きい頂点にフラグを立てることで管理をすることができます。

適切に実装を行うことで、全体の時間計算量を \(O(M\alpha(M))\) などにすることができます。

実装例は以下のようになります。

上で述べたふたつの辺の並びをナイーブに実装するのではなく、ある頂点を結んでいるすべての辺に対して、より大きい頂点と結ぶものかより小さい頂点と結ぶものかを判定することで実装をシンプルにしています。

#include <iostream>
#include <vector>
#include <atcoder/dsu>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;

    vector<vector<unsigned>> edge(N);
    for (unsigned i = 0; i < M; i++) {
        unsigned a, b;
        cin >> a >> b;
        edge[--a].push_back(--b);
        edge[b].push_back(a);
    }

    // 現在の連結成分数
    unsigned connected_components = 0;
    // これまで見た頂点のいずれかと隣接しているか
    vector<bool> already_connected(N);
    // 消すべき頂点の個数 = これまでに見た頂点と隣接している、まだ見ていない頂点の個数
    unsigned to_be_erased = 0;

    // 連結成分を管理する
    atcoder::dsu union_find(N);

    for (unsigned i = 0; i < N; i++) {
        // 頂点 i からなる連結成分を追加
        ++connected_components;
        // ここまでに見た頂点と隣接しているなら、
        if (already_connected[i]) {
            // 消すべき頂点が 1 つ減る
            --to_be_erased;
        }

        for (const auto j : edge[i])
            if (j < i) { // これまでに見た頂点側への辺なら、それを結ぶ
                // 異なる連結成分を結ぶ辺があれば、連結成分数が 1 つ減る
                if (!union_find.same(i, j)) {
                    union_find.merge(i, j);
                    --connected_components;
                }
            } else { // まだ見ていない頂点側への辺なら、フラグを立てる
                // これまで隣接したことがなかった頂点なら、消すべき頂点の個数が増える
                if (!already_connected[j])
                    ++to_be_erased;
                already_connected[j] = true;
            }

        // 番号が i より大きい頂点を全部消したときに連結なら、消すべき頂点を全部消すことで目標を達成できる
        if (connected_components == 1)
            cout << to_be_erased << '\n';
            // そうでないなら、不可能
        else
            cout << -1 << '\n';
    }

    return 0;
}