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;
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PI; 
typedef pair<LL,LL> PLL;
typedef unsigned long long ULL;
typedef pair<double,double> PD;

#define FOR(x, b, e) for(int x = b; x<= (e); x++)
#define FORD(x, b, e) for(int x = b; x>= (e); x--)
#define REP(x, n) for(int x = 0; x<(n); ++x)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())

#define PB push_back
#define IN insert
#define ST first
#define ND second
#define INF 2000000011
#define MOD 1000000007

#define MAXSIZE 400

VI graf[MAXSIZE];
int zaj[MAXSIZE];

int wyn=INF;
int ciag[MAXSIZE];

int n,m,k;

VI test;

void komb(int a,int b,int k){
	if(k){
		FOR(i,a,b){
			zaj[i]=1;
			komb(i+1,b,k-1);
			zaj[i]=0;
		}
	}
	else{
		int t=0;
		
		FOR(i,1,n)
			ciag[i]=1;
			
		FOR(i,1,n){
			if(!zaj[i]){
				REP(j,SIZE(graf[i]))
					ciag[graf[i][j]]=max(ciag[graf[i][j]],ciag[i]+1);
				t=max(t,ciag[i]);
			}
		}
		wyn=min(wyn,t);
	}
}

int main(){

	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>m>>k;
	
	REP(i,m){
		int a,b;
		cin>>a>>b;
		graf[a].PB(b);
	}
		
	if(k<=2)
		komb(1,n,k);
	else
		komb(max(1,n/2-25),min(n,n/2+25),k);
	
	cout<<wyn;
	
	return 0;
}