#include <bits/stdc++.h>

using namespace std;
int a[100000], b[100000];

int main()
{
    int n, m, k, ii, jj, ans = 0;
    cin >> n >> m >> k;
    if (k == 1)
        ans = n;
    for (int i = 0; i < n; i++)
    {
        a[i] = 1;
        b[i] = i;
    }
    for (int i = 0; i < m; i++)
    {
        cin >> ii >> jj;
        ii--;
        jj--;
        //b[jj] - кому принадлежит jj
        //a[b[jj]] - сколько владений у правителя jj
        if (a[b[jj]] == k)
            ans--;
        a[b[jj]]--;
        b[jj] = b[ii];
        a[b[ii]]++;
        if (a[b[ii]] == k)
            ans++;
        /*for (int i = 0; i < n; i++)
            cout << b[i] << " ";
        cout << "ans = ";*/
        cout << ans << endl;
    }
    return 0;
}