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
#include<bits/stdc++.h>
using namespace std;
#define maxn 302
#define inf 1000000000

int n, m, k, odp=inf;
int a, b, maksi, c;
int len[maxn];
vector<int> v[maxn], prey[5];
bool been[maxn], hunted[maxn], blocked[maxn];

void ini(int w){
	bool ok=0;
	for(int i=0; i<v[w].size(); i++){
		int u=v[w][i];
		if(blocked[u]) continue;
		ok=1;
		if(len[u]==0) ini(u);
		len[w]=max(len[w], len[u]+1);
	}
	if(ok==0) len[w]=1;
	maksi=max(maksi, len[w]);
}

void hunt(int w){
	hunted[w]=1;
	for(int i=0; i<v[w].size(); i++){
		int u=v[w][i];
		if(!hunted[u] && len[u]>=len[w]-1 && !blocked[u]){
			prey[c].push_back(u);
			hunt(u);
		}
	}
}

void find_prey(){
	maksi=0;
	fill(len, len+n+1, 0);
	prey[c].clear();
	fill(hunted, hunted+n+1, 0);
	for(int i=1; i<=n; i++){
		if(len[i]==0 && !blocked[i]) ini(i);
	}
	for(int i=1; i<=n; i++){
		if(len[i]==maksi && !blocked[i]){ 
			prey[c].push_back(i);
			hunt(i);
			break;
		}
	}
}

void go(int x){
	c=x;
	if(x==k){
		maksi=0;
		fill(len, len+n+1, 0);
		for(int i=1; i<=n; i++){
			if(len[i]==0 && !blocked[i]) ini(i);
		}
		odp=min(odp, maksi);
		return;
	}
	find_prey();
	for(int j=0; j<prey[x].size(); j++){
		blocked[prey[x][j]]=1;
		go(x+1);
		blocked[prey[x][j]]=0;
	}
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1; i<=m; i++){
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
	}
	go(0);
	if(odp==1) printf("0\n");
	else printf("%d\n", odp);
}