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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef __int128_t i128;
typedef __uint128_t u128;

ll mod=1000000000000000003;

const int N=101000,K=55;
struct Mod64 {
	Mod64():n_(0) {}
	Mod64(u64 n):n_(init(n)) {}
	static u64 init(u64 w) { return reduce(u128(w) * r2); }
	static void set_mod(u64 m) {
		mod=m; assert(mod&1);
		inv=m; rep(i,0,5) inv*=2-inv*m;
		r2=-u128(m)%m;
	}
	static u64 reduce(u128 x) {
		u64 y=u64(x>>64)-u64((u128(u64(x)*inv)*mod)>>64);
		return ll(y)<0?y+mod:y;
	}
	Mod64& operator += (Mod64 rhs) { n_+=rhs.n_-mod; if (ll(n_)<0) n_+=mod; return *this; }
	Mod64 operator + (Mod64 rhs) const { return Mod64(*this)+=rhs; }
	Mod64& operator -= (Mod64 rhs) { n_-=rhs.n_; if (ll(n_)<0) n_+=mod; return *this; }
	Mod64 operator - (Mod64 rhs) const { return Mod64(*this)-=rhs; }
	Mod64& operator *= (Mod64 rhs) { n_=reduce(u128(n_)*rhs.n_); return *this; }
	Mod64 operator * (Mod64 rhs) const { return Mod64(*this)*=rhs; }
	u64 get() const { return reduce(n_); }
	static u64 mod,inv,r2;
	u64 n_;
}f[N][K],one,zero;
u64 Mod64::mod,Mod64::inv,Mod64::r2;

mt19937_64 mrand(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rnd(ll x) { return mrand() % x;}
Mod64 powmod(Mod64 a,ll b) { Mod64 res=one; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}

int n,m,k,deg[N],pos[K],c[K];
Mod64 x[K],base[K][K];
ll ans[K];
VI e[N],rev[N];
int main() {
	Mod64::set_mod(mod);
	scanf("%d%d%d",&n,&m,&k);
	rep(i,0,m) {
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].pb(v);
		rev[v].pb(u);
		deg[v]++;
	}
	one=Mod64(1);
	rep(i,1,k+1) {
		f[i][i-1]=one;
	}
	queue<int> q;
	rep(i,1,n+1) if (deg[i]==0) {
		q.push(i);
	}
	while (!q.empty()) {
		int u=q.front(); q.pop();
		for (auto v:e[u]) {
			--deg[v];
			if (deg[v]==0) {
				if (v>k) {
					for (auto w:rev[v]) {
						Mod64 coef(rnd(mod));
						rep(j,0,k) f[v][j]+=coef*f[w][j];
					}
				}
				q.push(v);
			}
		}
	}
	rep(j,0,k) pos[j]=n+1;
	per(i,k+1,n+1) {
		rep(j,0,k) x[j]=f[i][j];
		int p=i;
		per(j,0,k) {
			if (x[j].n_==0) continue;
			if (base[j][j].n_==0) {
				rep(l,0,j+1) base[j][l]=x[l]; pos[j]=p;
				break;
			} else {
				if (pos[j]>p) {
					swap(pos[j],p); rep(l,0,j+1) swap(base[j][l],x[l]);
				}
				Mod64 v=x[j]*powmod(base[j][j],mod-2);
				rep(l,0,j+1) x[l]-=base[j][l]*v;
			}
		}
		rep(j,0,k) c[j]=pos[j];
		sort(c,c+k);
		rep(j,0,k) ans[j+1]+=n+1-c[j];
		ans[0]+=n+1-i;
	}
	rep(i,0,k+1) printf("%lld\n",ans[i]-ans[i+1]);
}