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
#include <bits/stdc++.h>

using namespace std;

long long n,m,k,a,b,v[300],l[4],h,w=LLONG_MAX;
vector <long long> t[300];

long long dfs(long long a, long long d, long long v1, long long v2, long long v3, long long v4) {
	long long w=d;
	if (v[a]==h) {++v[a];}
	for (long long i=0; i<t[a].size(); ++i) {
		if (t[a][i]!=v1&&t[a][i]!=v2&&t[a][i]!=v3&&t[a][i]!=v4) {
			w=max(w,dfs(t[a][i],d+1,v1,v2,v3,v4));
		}
	}
	return w;
}

long long path(long long v1, long long v2, long long v3, long long v4) {
	long long w=0;
	for (long long i=0; i<n; ++i) {
		if (v[i]==h&&i!=v1&&i!=v2&&i!=v3&&i!=v4) {
			w=max(w,dfs(i,1,v1,v2,v3,v4));
		} else if (v[i]==h) {
			++v[i];
		}
	}
	++h;
	return w;
}

int main() {
	scanf("%lld %lld %lld",&n,&m,&k);
	for (long long i=0; i<m; ++i) {
		scanf("%lld %lld",&a,&b);
		t[a-1].push_back(b-1);
	}
	if (k==n) {
		printf("0\n");
	} else {
		if (k>0) {
			for (long long a=0; a<n; ++a) {
				if (k>1) {
					for (long long b=a+1; b<n; ++b) {
						if (k>2) {
							for (long long c=b+1; c<n; ++c) {
								if (k>3) {
									for (long long d=c+1; d<n; ++d) {
										w=min(w,path(a,b,c,d));
									}
								} else {
									w=min(w,path(a,b,c,-1));
								}
							}
						} else {
							w=min(w,path(a,b,-1,-1));
						}
					}
				} else {
					w=min(w,path(a,-1,-1,-1));
				}
			}
		} else {
			w=min(w,path(-1,-1,-1,-1));
		}
		printf("%lld\n",w);
	}
	return 0;
}