1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <set>
#include <vector>

using namespace std;

const int MAXN = 300010;
const int MAXK = 51;

int furthest[MAXN][MAXK];
set<int> G[MAXN];


long long out[MAXK];
bool vis[MAXN];
int visq[MAXN];
int visc = 0;



bool lej_cole_DFS(int v, int sink) {
  vis[v] = true;
  visq[visc] = v;
  visc++;

  if (v == sink) {
    return true;
  }

  for (int succ : G[v]) {
    if (!vis[succ]) {
      if (lej_cole_DFS(succ, sink)) {
        G[v].erase(succ);
        G[succ].insert(v);
        return true;
      }
    }
  }

  return false;
}

bool lej_cole(int source, int sink) {
  bool retv = lej_cole_DFS(source, sink);
  for (int i = 0; i < visc; i++) {
    vis[visq[i]] = false;
  }
  visc = 0;
  return retv;
}


int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  int sink = 2*n + 1;

  for (int i = 1; i <= k; i++) {
    G[0].insert(i);
  }

  for (int i = k + 1; i <= n; i++) {
    G[i + n].insert(i);
  }

  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    G[x].insert(y + n);

  }


  for (int outk = 0; outk <= k; outk++) {
    int r = k;
    int max_conk = 0;
    for (int l = k + 1; l <= n; l++) {
      while (r < n && max_conk <= outk) {
        r++;
        G[r].insert(sink);
        if (lej_cole(0, sink)) {
          max_conk++;
        }
      }

      if (max_conk > outk) {
        lej_cole(r, 0);
        G[sink].erase(r);
        max_conk--;
        r--;
      }
      furthest[l][outk] = r;

      if (G[sink].find(l) != G[sink].end()) {
        lej_cole(l, 0);
        G[sink].erase(l);
        max_conk--;
        if (lej_cole(0, sink)) {
          max_conk++;
        }
      }
      if (G[l].find(sink) != G[l].end()) {
        G[l].erase(sink);
      }
      if (r < l) {
        r++;
      }
    }

    while (lej_cole(sink, 0)) {};
    for (int i = 1; i <= n; i++) {
      G[i].erase(sink);
    }
  }

  for (int l = k + 1; l <= n; l++) {
    out[0] += furthest[l][0] - l + 1;
    for (int i = 1; i <= k; i++) {
      out[i] += furthest[l][i] - furthest[l][i - 1];
    }
  }

  for (int i = 0; i <= k; i++) {
    printf("%lld\n", out[i]);
  }
}