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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
#include <cstdio>
#include <cassert>
#include <vector>
#include <cinttypes>
#include <set>

typedef long long ll;

// For any value K, and for any L, we want to find the highest value R
// for which f(L,R) = K.
#define MAXN 200100
#define MAXM 1000100
#define MAXK 55
int highest[MAXN][MAXK];

// At any point in time, we'll have a path-set constructed through the graph,
// for some [L,R], 
// If f(L,R) is K, then we'll need to check f(L,R+1) in our search for the highest R.
// If f(L,R) is K+1, then we know f(L,R-1) was K, so we found the value.
//   in this case, we'll check f(L+1,R). It's going to either be K (in which case we're
//   back to increasing R), or K+1 (in which case we know again that's the optimal
//   value for L+1. 
int N, M, globalK;

// The number of paths will either be K, in which case we know
// f(L-1,R)  K+1, or K+1, in which case we know f(L-1,R) = K.
// The current BFS is valid for [currL, currR] (inclusive on both sides).
int currL;
int currR;

std::vector<int> neiup[MAXN];  // This is the upstream neighbours.
std::vector<int> neidown[MAXN];  // Downstream neighbours.
int chosenup[MAXN];  // The path we take from this vertex, or -1 if none. 
int parent[MAXN];  // Where did we come from to this vertex, or -1 if none.

int queue[MAXN];
int queuebeg;
int queueend;
int popqueue() { return queue[queuebeg++]; }
void pushqueue(int val) { queue[queueend++] = val; }
bool queueempty() { return queuebeg == queueend; } 

// We double the graph vertices. Vertex A is represented by 2A, 2A+1. The
// incoming edges are to 2A, there's an edge 2A -> 2A+1, and outgoing edges
// are from 2A+1.
// We seek paths to top (even) vertices  <= 2globalK
// We seek paths from lower (odd) vertices.
int curparent[MAXN];  // The parent of this vertex in the current run of the BFS.
bool reverseedge[MAXN];  // True if the edge from X to curparent[X] is going up (reverse ex. edge)  
bool visited[MAXN];  // Have we been here in the current run of the BFS.


void printBfs() {
  std::set<int> visited;
  for (int k = 2; k <= 2 * globalK; k += 2) {
    if (parent[k] != -1) {
      fprintf(stderr, "%d[0]", k/2); 
      int v = k;
      while (v != -1) {
        visited.insert(v); 
        if (parent[v] != -1 && chosenup[parent[v]] != v) fprintf(stderr, "Will crash, v=%d[%d], parent = %d[%d], chosenup = %d[%d]\n", v/2, v&1, parent[v]/2, parent[v]&1, chosenup[parent[v]]/2, chosenup[parent[v]]&1);
        if (parent[v] != -1) assert(chosenup[parent[v]] == v);
        v = parent[v];
        if (v != -1) fprintf(stderr, "->%d[%d]", v/2, v&1); 
      }
      fprintf(stderr, "\n");
    }
  } 
  for (int n = 2; n <= N; ++n) if (visited.find(n) == visited.end()) {
    assert(chosenup[n] == -1);
    assert(parent[n] == -1);
  }
}

// We try to increase R (adding one source), and see what happens.
// Return true if we extended the graph (so, observed K increased by 1).
bool addToR() {
  queuebeg = 0;
  queueend = 0;
  pushqueue(2 * currR + 3);
  visited[2 * currR + 3] = true;
  while (!queueempty()) {
    int cvert = popqueue();
    if (cvert <= 2 * globalK && (cvert % 2 == 0)) {
      // Success. We found a path to a yet-unused target vial!
      assert(chosenup[cvert] == -1);
      while (cvert != 2 * currR + 3) {
        if (reverseedge[cvert]) {   
          if (parent[curparent[cvert]] == cvert) parent[curparent[cvert]] = -1;
          if (chosenup[cvert] == curparent[cvert]) chosenup[cvert] = -1;
        } else { 
          parent[cvert] = curparent[cvert];
          chosenup[curparent[cvert]] = cvert;
        }
        cvert = curparent[cvert];
      } 
      for (int i = 0; i < queueend; ++i) visited[queue[i]] = false;
      return true; 
    }
    if (parent[cvert] != -1) {
      int nextvert = parent[cvert];
      if (!visited[nextvert]) {
        // We went down, so it can't be an unvisited source.
        curparent[nextvert] = cvert;
        reverseedge[nextvert] = true;
        visited[nextvert] = true;
        pushqueue(nextvert); 
      }
    }
    for (int nextvert : neiup[cvert]) {
      if (visited[nextvert]) continue;
      if (nextvert == chosenup[cvert]) continue;
      curparent[nextvert] = cvert;
      visited[nextvert] = true;
      reverseedge[nextvert] = false;
      pushqueue(nextvert); 
    }
  }
  // Failed to find an extending path. Clean up the visited array.
  for (int i = 0; i < queueend; ++i) visited[queue[i]] = false;
  return false;
}

// Return true if the graph is smaller now (that is, if K is smaller).
bool removeFromL() {
  if (chosenup[2 * currL + 1] == -1) {
    // L is not even a part of a BFS path.
    return false;
  }  
  if (parent[2 * currL + 1] != - 1) {
    // L is in the middle of a BFS path, it's not the source.
    return false;
  }
  // Now currL is the start of a BFS path. Let's try correcting it.
  queuebeg = 0;
  queueend = 0;
  pushqueue(2 * currL + 1);
  visited[2 * currL + 1] = true;
  while (!queueempty()) {
    int cvert = popqueue();
    if (cvert >= 2 * currL + 2 && cvert <= 2 * currR + 1 && (cvert % 2 == 1)) {
      // Success - we found a path to a yet-unused vertex in range.
      while (cvert != 2 * currL + 1) {
        if (reverseedge[cvert]) {
          if (parent[cvert] == curparent[cvert]) parent[cvert] = -1;
          if (chosenup[curparent[cvert]] == cvert) chosenup[curparent[cvert]] = -1; 
        } else {
          chosenup[cvert] = curparent[cvert];
          parent[curparent[cvert]] = cvert;
        }
        cvert = curparent[cvert];
      } 
      for (int i = 0; i < queueend; ++i) visited[queue[i]] = false;
      return false;
    }
    for (int nextvert : neidown[cvert]) {
      if (visited[nextvert]) continue;
      if (nextvert == parent[cvert]) continue;
      curparent[nextvert] = cvert;
      reverseedge[nextvert] = false;
      visited[nextvert] = true;
      pushqueue(nextvert);
    }   
    if (chosenup[cvert] != -1) {
      int nextvert = chosenup[cvert];
      if (!visited[nextvert]) {   
        curparent[nextvert] = cvert;
        reverseedge[nextvert] = true;
        visited[nextvert] = true;
        pushqueue(nextvert);
      }
    }   
  }  
  for (int i = 0; i < queueend; ++i) visited[queue[i]] = false;
  int cvert = 2 * currL + 1;
  while (cvert != -1) {
    int next = chosenup[cvert];
    chosenup[cvert] = -1;
    parent[next] = -1;
    cvert = next;
  }
  return true;
}

int chosenUpBak[MAXN];
int parentBak[MAXN]; 

int prevHighest(int l, int k) {
  if (k) return highest[l][k-1];
  return l-1;
}

int main() {
  scanf("%d %d %d", &N, &M, &globalK);
  for (int i = 1; i <= N; ++i) {
    neidown[2 * i].push_back(2 * i + 1);
    neiup[2 * i + 1].push_back(2 * i);    
  }
  N *= 2;
  N += 1;
  for (int i = 0; i < M; ++i) {
    int A, B;
    scanf("%d %d", &A, &B);
    neidown[2 * A + 1].push_back(2 * B);
    neiup[2 * B].push_back(2 * A + 1);
  }
  for (int i = 0; i <= N; ++i) { chosenUpBak[i] = parentBak[i] = -1; visited[i] = false; }
  int currRBak = globalK; 
  for (int K = 0; K <= globalK; ++K) {
    currL = globalK + 1; 
    currR = currRBak;
    int observedK = K;
    for (int i = 0; i <= N; ++i) { chosenup[i] = chosenUpBak[i]; parent[i] = parentBak[i]; }
    while(currR <= N / 2 && observedK <= K) {
      if (addToR()) observedK += 1;
      currR += 1;
    }
    highest[globalK + 1][K] = currR - 1; 
    for (int i = 1; i <= N; ++i) { chosenUpBak[i] = chosenup[i]; parentBak[i] = parent[i]; } currRBak = currR; 
    // Now, move right.
    while (currR <= N / 2 && currL < N / 2) {
      // We're currently set up at currL, currR, and the value is one too large.
      if (removeFromL()) observedK -= 1;
      currL += 1;
      while (currR <= N / 2 && observedK <= K) {
        if (addToR()) observedK += 1;
        currR += 1;
      }
      highest[currL][K] = currR - 1;
    } 
    if (currR > N / 2) {
      currL += 1;
      for (; currL <= N/2; ++currL) {
        highest[currL][K] = currR - 1;
      }
    }
  }
  for (int k = 0; k <= globalK; ++k) {
    ll res = 0;
    for (int n = globalK + 1; n <= N/2; ++n) {
      res += highest[n][k] - prevHighest(n, k);
    }
    printf("%" PRId64 "\n", res);
  }
}