#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/*
#pragma GCC target("avx2")
#pragma GCC optimization("Ofast")
#pragma GCC optimization("unroll-loops")
*/

using namespace __gnu_pbds;
using namespace std;

#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define vt vector
#define maxi(x,y) x=max(x,y)
#define mini(x,y) x=min(x,y)
#define size(x) (int)x.size()
#define all(r) begin(r),end(r)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define cx real()
#define cy imag()
#define precision(x) setprecision(x)<<fixed
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#ifndef DEBUG
#define DEBUG false
#endif
#define dbg if(DEBUG)

typedef long long ll;
typedef long double ld;
typedef complex<long double> cplx;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef vt<int> vi;
typedef vt<vi> vvi;
typedef vt<bool> vb;
typedef vt<vb> vvb;
typedef vt<char> vc;
typedef vt<vc> vvc;
typedef vt<string> vs;
typedef vt<vs> vvs;
typedef vt<ll> vll;
typedef vt<vll> vvll;
typedef vt<ld> vld;
typedef vt<vld> vvld;
typedef vt<cplx> vcplx;
typedef vt<vcplx> vvcplx;

template<typename T>
using ordset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T1,typename T2>
ostream& operator<<(ostream &os,pair<T1,T2>& VAR){
	os<<"("<<VAR.e1<<","<<VAR.e2<<")";
	return os;
}

template<typename T>
ostream& operator<<(ostream& os,vt<T>& VAR){
	os<<"[";
	for(int i=0;i<size(VAR)-1;i++)
		os<<VAR[i]<<",";
	if(size(VAR))
		os<<VAR.back();
	os<<"]";
	return os;
}

template<typename T>
istream& operator>>(istream& is,complex<T>& VAR){
	T value;
	is>>value;
	VAR.real(value);
	is>>value;
	VAR.imag(value);
	return is;
}

const bool TESTS=false;

struct edge{
	int v,rev,cap,flow;
	edge(int V,int REV,int CAP,int FLOW):v(V),rev(REV),cap(CAP),flow(FLOW){}
};

const int MAXN=1e5+10;

const int source=0;
const int sink=MAXN*3-1;
int total_flow=0;

vt<edge> g[MAXN*3];
bitset<MAXN*3> legal;

//2x-1 => in  node
//2x   => out node

int flow_query_id=0;

int vis[MAXN*3];
int prv[MAXN*3];

void add_flow(){
	flow_query_id++;
	vis[source]=flow_query_id;
	vi q={source};
	while(size(q)&&vis[sink]!=flow_query_id){
		int u=q.back();
		q.pop_back();
		for(auto& e:g[u])
			if(legal[e.v]&&vis[e.v]!=flow_query_id&&e.cap-e.flow>0){
				vis[e.v]=flow_query_id;
				prv[e.v]=e.rev;
				q.eb(e.v);
			}
	}
	if(vis[sink]!=flow_query_id)
		return;
	int u=sink;
	while(u!=source){
		g[u][prv[u]].flow=-1;
		int v=g[u][prv[u]].v;
		g[v][g[u][prv[u]].rev].flow=1;
		u=v;
	}
	total_flow++;
}

void remove_vertex(int node){
	legal[node*3]=false;
	if(g[node*3][0].flow==0)
		return;
	int u=node*3;
	while(u!=source){
		for(auto& e:g[u])
			if(e.flow==-1){
				e.flow=g[e.v][e.rev].flow=0;
				u=e.v;
				break;
			}
	}
	u=node*3;
	while(u!=sink){
		for(auto& e:g[u])
			if(e.flow==1){
				e.flow=g[e.v][e.rev].flow=0;
				u=e.v;
				break;
			}
	}
	total_flow--;
	add_flow();
}

void add_vertex(int node){
	legal[node*3]=true;
	add_flow();	
}

void add_edge(int u,int v){
	g[u].pb(edge(v,size(g[v]),1,0));
	g[v].pb(edge(u,size(g[u])-1,0,0));
}

const int MAXM=1e6+10;

pair<int,int> edg[MAXM];

void solve(){
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		add_edge(i*3-2,i*3-1);
	for(int i=1;i<=k;i++)
		add_edge(source,i*3-2);
	for(int i=k+1;i<=n;i++){
		add_edge(i*3-1,i*3);
		add_edge(i*3,sink);
	}
	legal[source]=true;
	legal[sink]=true;
	for(int i=1;i<=n;i++)
		legal[i*3-2]=legal[i*3-1]=true;
	for(int i=0;i<m;i++)
		cin>>edg[i].e1>>edg[i].e2;
	mt19937 rng(2137);
	shuffle(edg,edg+m,rng);
	for(int i=0;i<m;i++)
		add_edge(edg[i].e1*3-1,edg[i].e2*3-2);
	vll ans(k+2,0);
	ans[0]=(1ll*(n-k)*(n-k+1))/2ll;
	for(int cnt=1;cnt<=k;cnt++){
		for(int i=k+1;i<=n;i++)
			legal[i*3]=false;
		for(auto& e:g[sink])
			e.flow=0;
		for(int i=1;i<=n*3;i++)
			for(auto& e:g[i])
				e.flow=0;
		for(auto& e:g[source])
			e.flow=0;
		total_flow=0;
		int r=k+1;
		for(int i=k+1;i<=n;i++){
			if(i-1>=k+1)
				remove_vertex(i-1);
			while(r<=n&&total_flow<cnt){
				add_vertex(r);
				r++;
			}
			if(total_flow==cnt)
				ans[cnt]+=n-r+2;
		}
	}
	for(int i=0;i<=k;i++)
		cout<<ans[i]-ans[i+1]<<'\n';
}

int32_t main(){
	fastio;
	if(TESTS){
		int TEST_COUNT;
		cin>>TEST_COUNT;
		for(int i=0;i<TEST_COUNT;i++)
			solve();
	}
	else
		solve();
	return 0;
}