Trips cf-1037E

//Trips cf-1037E

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


const int N = 2e5 + 4 ;
set <int> G[N] ;

struct data {
    int u , v ;
}edge[N];


int marked[N] ;
int deg[N] ;
int res[N] ;

int main () {
    int n , m , k ;
    cin >> n >> m >> k ;
    for (int i = 1 ; i <= m ; i++) {
        scanf("%d %d" , &edge[i].u,&edge[i].v) ;
        G[edge[i].u].insert(edge[i].v) ;
        G[edge[i].v].insert(edge[i].u) ;
    }

    vector <int> useless ;
    int ans = n ;
    for (int i = 1 ; i <= n ; i++) {
        if (G[i].size() < k) {
            marked[i] = 1 ;
            ans-- ;
            useless.push_back(i) ;
        }
    }

    for (int i = m ; i >= 1 ; i--) {
        while(useless.size() > 0) {
            int u = useless.back() ;
            useless.pop_back() ;
            for (auto v : G[u]) {
                G[v].erase(u) ;
                if (marked[v] == 0 and G[v].size() < k) {
                    useless.push_back(v) ;
                    marked[v] = 1 ;
                    ans-- ;
                }
            }
            G[u].clear() ;
        }

        res[i] = ans ;
        int u = edge[i].u , v = edge[i].v ;

        if (marked[u] or marked[v]) continue ;
        G[u].erase(v) ;
        G[v].erase(u) ;
        if (G[u].size() < k) {
            useless.push_back(u) ;
            ans-- ;
            marked[u] = 1 ;
        }
        if (G[v].size() < k) {
            useless.push_back(v) ;
            ans-- ;
            marked[v] = 1;
        }
    }

    for (int i = 1 ; i <= m ; i++) printf ("%d\n" , res[i]) ;

    return 0 ;
}