/*
author:yllcm
link:https://loj.ac/s/1969842
*/
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 1e5 + 10;
const int P = 1e9 + 7;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int ksm(int x, int k) {
  int res = 1;
  for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
  return res;
}
typedef vector<int> vec;
int n, m, k;
int in[N];
vec f[N];
vector<pii> G[N];
vec operator + (vec x, vec y) {
  vec z(k);
  for(int i = 0; i < k; i++)z[i] = (x[i] + y[i]) % P;
  return z;
}
vec operator - (vec x, vec y) {
  vec z(k);
  for(int i = 0; i < k; i++)z[i] = (x[i] - y[i] + P) % P;
  return z;
}
vec operator * (vec x, int y) {
  vec z(k);
  for(int i = 0; i < k; i++)z[i] = 1ll * x[i] * y % P;
  return z;
}
void topo() {
  queue<int> q;
  for(int i = 0; i < n; i++)if(!in[i])q.push(i);
  while(q.empty() == false) {
    int u = q.front(); q.pop();
    for(auto t : G[u]) {
      int v = t.FR, w = t.SE;
      f[v] = f[v] + f[u] * w;
      if(!(--in[v]))q.push(v);
    }
  }
  return ;
}
ll ans[N];
struct Basis {
  vec f[N];
  int vis[N], mx[N], inv[N];
  void init() {
    for(int i = 0; i < k; i++)vis[i] = 0;
    return ;
  }
  bool ins(vec x, int id) {
    for(int i = 0; i < k; i++) {
      if(!x[i])continue;
      if(!vis[i]) {
        vis[i] = true; mx[i] = id; f[i] = x;
        return true;
      }
      else if(id < mx[i])swap(f[i], x), swap(mx[i], id);
      int r = 1ll * x[i] * ksm(f[i][i], P - 2) % P;
      x = x - f[i] * r;
    }
    return false;
  }
}bs;
int main() {
  n = read(); m = read(); k = read();
  mt19937_64 rnd(114514);
  for(int i = 1; i <= m; i++) {
    int u = read() - 1, v = read() - 1;
    G[u].pb({v, rnd() % P}); in[v]++;
  }
  for(int i = 0; i < n; i++)f[i].resize(k);
  for(int i = 0; i < k; i++)f[i][i] = 1;
  topo();
  for(int i = n - 1; i >= k; i--) {
    bs.ins(f[i], i);
    vector<int> pt = {i, n};
    for(int i = 0; i < k; i++)if(bs.vis[i])pt.pb(bs.mx[i]);
    sort(pt.begin(), pt.end());
    for(int i = 0; i + 1 < pt.size(); i++)ans[i] += pt[i + 1] - pt[i];
  }
  for(int i = 0; i <= k; i++)printf("%lld\n", ans[i]);
  return 0;
}