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
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int M=1e6;
const int K=50;
vector<int> e[2*N+10];
int mtch[2*N+10];
long long ans[K+10];
int r[K+10];
bool vis[2*N+10];
bool dfs(int x)
{
	vis[x]=true;
	for(auto v:e[x])
	{
		//cerr<<x<<": "<<v<<" "<<mtch[v]<<"\n";
		if(mtch[v]==-1)
		{
			mtch[v]=x;
			mtch[x]=v;
			return true;
		}
	}
	for(auto v:e[x])
	{
		//cerr<<x<<": "<<v<<" "<<mtch[v]<<"\n";
		if(!vis[mtch[v]] && dfs(mtch[v]))
		{
			mtch[v]=x;
			mtch[x]=v;
			return true;
		}
	}
	return false;
}
bool check(int x,int n,int ll,int rr)
{
	if(!e[x].empty() && e[x].back()==n+x)
		e[x].pop_back();
	if(mtch[n+x]!=0 && mtch[n+x]!=-1)
	{
		mtch[mtch[n+x]]=-1;
		mtch[n+x]=0;
	}
	for(int i=1;i<=n;i++)
		vis[i]=false;
	for(int i=n;i>=1;i--)
	{
		if(!vis[i] && mtch[i]==-1 && dfs(i))
			return true;
	}
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	vis[0]=true;
	mtch[0]=0;
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[b].push_back(n+a);
	}
	for(int i=1;i<=k;i++)
		r[i]=k+i;
	for(int l=k+1;l<=n;l++)
	{
		for(int i=1;i<=k;i++)
			mtch[n+i]=mtch[i]=-1;
		for(int i=k+1;i<=n;i++)
		{
			mtch[n+i]=i;
			mtch[i]=n+i;
			if(e[i].empty() || e[i].back()!=n+i)
				e[i].push_back(n+i);
		}
		r[0]=l;
		for(int i=1;i<=k;i++)
		{
			r[i]=max(r[i],r[i-1]);
			for(int j=r[i-1];j<min(n+1,r[i]);j++)
			{
				if(mtch[n+j]!=0 && mtch[n+j]!=-1)
				{
					mtch[mtch[n+j]]=-1;
					mtch[n+j]=0;
				}
				if(!e[j].empty() && e[j].back()==n+j)
					e[j].pop_back();
			}
			//cerr<<i<<" "<<l<<" "<<r[i]<<"\n";
			while(r[i]<=n && !check(r[i],n,l,r[i]))
				r[i]++;
			r[i]=min(n+1,r[i]);
			ans[i-1]+=r[i]-r[i-1];
			//cerr<<i<<" ["<<l<<","<<r[i]<<"]\n\n";
		}
		ans[k]+=n+1-r[k];
	}
	for(int i=0;i<=k;i++)
		cout<<ans[i]<<"\n";
	return 0;
}