1. Solving the decision problem

First, let us consider if the condition can be satisfied for a given \(k\).

If one cannot travel from vertex \(1\) to vertex \(i\ (1\lt i\leq k)\) without passing through a vertex greater than \(k\), then the condition cannot be satisfied. This is equivalent to whether vertices \(1\) and \(i\) belongs to the same connected component when all vertices greater than \(k\) are removed.

Conversely, if there only one connected component after removing vertices greater than \(k\), then the condition can be satisfied.

This can be checked by using a Disjoint Set Union (DSU).

Now let us consider how to decide it for all \(k\).

If we add edges to the DSU in ascending order of the larger of the vertices that each edge connects, the connectivity can be checked at an appropriate moment for each \(k\).

2. Solving the minimization problem

Next, let us consider how to find the minimum number of vertices required to be removed.

Any vertices adjacent to a vertex less than or equal to \(k\) must be removed. Conversely, all the other vertices may be retained.

Such edges can be managed by maintaining the edges in ascending order of the smaller of the vertices that each edge connects, and flagging the larger vertex.

With appropriate implementation, the overall time complexity can be \(O(M\alpha(M))\).

Sample code is shown below.

Instead of directly maintaining the two sequences of edges, for all edges incident to each vertex, we check if it connects with a larger vertex or a smaller vertex, to simplify the implementation.

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

    // Current number of connected components
    unsigned connected_components = 0;
    // Whether it is adjacent to any of the vertex inspected so far
    vector<bool> already_connected(N);
    // The number of vertices to be removed = the number of uninspected vertices adjacent to a vertex seen so far
    unsigned to_be_erased = 0;

    // Manages connected components
    atcoder::dsu union_find(N);

    for (unsigned i = 0; i < N; i++) {
        // Add a connected component consisting of vertex i
        ++connected_components;
        // If it is adjacent to any vertex inspected so far,
        if (already_connected[i]) {
            // the number of vertices to be removed decreases by one.
            --to_be_erased;
        }

        for (const auto j : edge[i])
            if (j < i) { // If it goes to a vertex seen so far, connect it
                // If it connects different connected components, the number of connected components decreases by one
                if (!union_find.same(i, j)) {
                    union_find.merge(i, j);
                    --connected_components;
                }
            } else { // If it goes to a vertex not seen so far, flag it
                // If it has never become adjacent, this is a new vertex that needs to be removed
                if (!already_connected[j])
                    ++to_be_erased;
                already_connected[j] = true;
            }

        // If the graph is connected after removing all vertices greater than i, it can be achieved by removing all vertices to be removed
        if (connected_components == 1)
            cout << to_be_erased << '\n';
            // Otherwise, it is impossible
        else
            cout << -1 << '\n';
    }

    return 0;
}