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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <stdio.h>
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
const int C=501;

int ln[5][C], ded[C], sw[C], ij[C], lol[5];
vector <vector <int> > tab(C);


int F[C], d[C], par[C], asw[C];
int findlen(int n, vector <vector <int> > &gr, int ij[], int sw[], int dead[], int l[], int p){
	int i, j, iF=0, jF=0, mx=0, a;
	
	for (i=1;i<=n;i++)	{
		asw[i]=sw[i];
		if (asw[i]==0&&dead[i]==0)	F[jF]=i, d[i]=1, par[i]=-1, jF++;
	}
	if (jF==0)	return 0;
	for (iF=0;iF<jF;iF++){
		a=F[iF];
		if (d[a]>d[mx])	mx=a;
		for (j=0;j<ij[a];j++){
			asw[gr[a][j]]--;
			if (d[gr[a][j]]<d[a]+1)	d[gr[a][j]]=d[a]+1, par[gr[a][j]]=a;
			if (asw[gr[a][j]]==0&&dead[gr[a][j]]==0)	F[jF]=gr[a][j], jF++;
		}
	}
	j=0;
	for (i=a;i>=0;i=par[i])	l[j]=i, j++;
	lol[p]=j;
	mx=d[mx];
	for (i=1;i<=n;i++)	par[i]=0, d[i]=0;
	return mx;
}


void kill(int a){
	int i;
	ded[a]++;
	if (ded[a]>1)	return;
	for (i=0;i<ij[a];i++)	sw[tab[a][i]]--;
}

void lift(int a){
	int i;
	ded[a]--;
	if (ded[a]>0)	return;
	for (i=0;i<ij[a];i++)	sw[tab[a][i]]++;
}

int main(){
	srand(time(NULL));
	int n, m, k, i, j, a, b, i1, i2, i3, i4, zz, amx=1000;
	scanf ("%d %d %d", &n, &m, &k);
	for (i=0;i<m;i++)	scanf ("%d %d", &a, &b), tab[a].push_back(b), ij[a]++, sw[b]++;
	
	if (k>=n){
		printf ("%d\n", 0);
		return 0;
	}
	if (k==0)	amx=findlen(n, tab, ij, sw, ded, ln[0], 0);
	if (k==1){
		findlen(n, tab, ij, sw, ded, ln[0], 0);
		for (i1=0;i1<lol[0];i1++){
			kill(ln[0][i1]);
			zz=findlen(n, tab, ij, sw, ded, ln[1], 1);
			if (zz<amx)	amx=zz;			
			lift(ln[0][i1]);
		}
	}
	
	if (k==2){
		findlen(n, tab, ij, sw, ded, ln[0], 0);
		for (i1=0;i1<lol[0];i1++){
			kill(ln[0][i1]);
			findlen(n, tab, ij, sw, ded, ln[1], 1);
			for (i2=0;i2<lol[1];i2++){
				kill(ln[1][i2]);
				zz=findlen(n, tab, ij, sw, ded, ln[2], 2);
				if (zz<amx)	amx=zz;
				lift(ln[1][i2]);
			}	
			lift(ln[0][i1]);
		}
	}
	
	
	if (k==3){
		findlen(n, tab, ij, sw, ded, ln[0], 0);
		for (i1=0;i1<lol[0];i1++){
			kill(ln[0][i1]);
			findlen(n, tab, ij, sw, ded, ln[1], 1);
			for (i2=0;i2<lol[1];i2++){
				kill(ln[1][i2]);
				findlen(n, tab, ij, sw, ded, ln[2], 2);
				for (i3=0;i3<lol[2];i3++){
					kill(ln[2][i3]);
					zz=findlen(n, tab, ij, sw, ded, ln[3], 3);
					if (zz<amx)	amx=zz;
					lift(ln[2][i3]);
				}		
				lift(ln[1][i2]);
			}	
			lift(ln[0][i1]);
		}
	}
	
	if (k==4){
		findlen(n, tab, ij, sw, ded, ln[0], 0);
		for (i1=0;i1<lol[0];i1++){
			kill(ln[0][i1]);
			findlen(n, tab, ij, sw, ded, ln[1], 1);
			for (i2=0;i2<lol[1];i2++){
				kill(ln[1][i2]);
				findlen(n, tab, ij, sw, ded, ln[2], 2);
				for (i3=0;i3<lol[2];i3++){
					kill(ln[2][i3]);
					findlen(n, tab, ij, sw, ded, ln[3], 3);
					for (i4=0;i4<lol[3];i4++){
						kill(ln[3][i4]);
						zz=findlen(n, tab, ij, sw, ded, ln[4], 4);
						if (zz<amx)	amx=zz;
						lift(ln[3][i4]);
					}					
					lift(ln[2][i3]);
				}	
				lift(ln[1][i2]);
			}	
			lift(ln[0][i1]);
		}
	}
	
	printf ("%d\n", amx);
	
return 0;}