#include<bits/stdc++.h>
using namespace std;
const int Max_N=1e5,Max_M=1e6,Mod=(1e9)+7;
int n,m,K,Num,lin[Max_N+5],In[Max_N+5],a[55][55],f[55][Max_N+5],A[55],M[55][55],B[55],res[55];
long long ans[55];
queue<int> q;
struct Edge{
	int Id,Next;
} e[Max_M+5];
void Insert(int x,int y){
	e[++Num].Next=lin[x]; lin[x]=Num; e[Num].Id=y;
}
int Read(){
	int num=0; char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
	return num;
}
int Rand(){
	return (rand()*10000000ll+rand()*1000+rand())%(Mod-1)+1;
}
int Mul(int x,int y){
	int Ans=1;
	for(;y;y>>=1,x=1ll*x*x%Mod)
	 if(y&1) Ans=1ll*Ans*x%Mod;
	return Ans;
}
void Ins(int x){
	for(int i=0;i<K;i++) res[i]=f[i][x];
	for(int i=0;i<K;i++)
	 if(res[i]){
	 	if(!A[i]){
	 		A[i]=x;
	 		for(int j=0;j<K;j++)
			 M[i][j]=res[j];
			break;
		} else {
			if(A[i]<x){
				swap(A[i],x);
				for(int j=0;j<K;j++)
				 swap(M[i][j],res[j]);
			}
			int d=res[i]*Mul(M[i][i],Mod-2);
			for(int j=0;j<K;j++)
			 res[j]=(res[j]-1ll*d*M[i][j]%Mod+Mod)%Mod;
		}
	 }
}
int main(){
	srand(123456); 
	n=Read(),m=Read(),K=Read(); B[0]=K;
	for(int i=1;i<=m;i++){
		int u=Read(),v=Read();
		Insert(u,v); ++In[v];
	}
	for(int i=1;i<=n;i++)
	 if(!In[i]) q.push(i);
	for(;q.size();){
		int x=q.front(); q.pop();
		if(x<=K) f[x-1][x]=1;
		for(int i=lin[x];i;i=e[i].Next){
			int Rnd=Rand();
			for(int j=0;j<K;j++)
			 f[j][e[i].Id]=(1ll*f[j][e[i].Id]+1ll*f[j][x]*Rnd%Mod)%Mod;
			if(!(--In[e[i].Id])) q.push(e[i].Id);
		}
	}
	for(int x=K+1;x<=n;x++){
		Ins(x); int cnt=0;
		for(int i=0;i<K;i++) 
		 if(A[i]) B[++cnt]=A[i];
		sort(B+1,B+cnt+1);
		for(int i=1;i<=cnt;i++)
		 ans[cnt-i+1]+=B[i]-B[i-1];
		ans[0]+=x-B[cnt];
	}
	for(int i=0;i<=K;i++) printf("%lld\n",ans[i]);
	return 0;
}