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
#include<bits/stdc++.h>
using namespace std;
const int inf = 2e9+5;
const int N = 305;

int n,m,k;
vector<int> adj[N];
bool blok[N];
int dp[N];


int dpek() {
	
	for(int i = 1; i <= n; ++i) {
		dp[i] = 0;
	}
	
	int ret = 0;
	
	for(int i = n; i >= 1; --i) {
		
		if(blok[i]) continue;
		
		int mx = 0;
		
		for(int e : adj[i]) {
			mx = max(mx,dp[e]);
		}
		
		dp[i] = mx+1;
		ret = max(ret,dp[i]);
	}
	
	return ret;
}

int main() {
	scanf("%d%d%d",&n,&m,&k);
	
	for(int i = 1; i <= m; ++i) {
		int a,b; scanf("%d%d",&a,&b);
		adj[a].push_back(b);
	}
	
	int res = inf;
	
	if(k == 4) {
		for(int i = 1; i <= n; ++i) {
			for(int j = i+1; j <= n; ++j) {
				for(int y = j+1; y <= n; ++y) {
					for(int h = y+1; h <= n; ++h) {
						
						for(int x = 1; x <= n; ++x) 
							blok[x] = 0;
						
						blok[i] = 1;
						blok[j] = 1;
						blok[y] = 1;
						blok[h] = 1;
					
						res = min(res,dpek());
					}
				}
			}
		}
	}
	else if(k == 3) {
		for(int i = 1; i <= n; ++i) {
			for(int j = i+1; j <= n; ++j) {
				for(int y = j+1; y <= n; ++y) {
					
					for(int x = 1; x <= n; ++x) 
						blok[x] = 0;
						
					blok[i] = 1;
					blok[j] = 1;
					blok[y] = 1;					
				
					res = min(res,dpek());
				}
			}
		}
	}
	
	else if(k == 2) {
		for(int i = 1; i <= n; ++i) {
			for(int j = i+1; j <= n; ++j) {
				
				for(int x = 1; x <= n; ++x) 
					blok[x] = 0;				
				
				blok[i] = 1;
				blok[j] = 1;
			
				res = min(res,dpek());
			}
		}
	}
	else if(k == 1) {
		for(int i = 1; i <= n; ++i) {

			for(int x = 1; x <= n; ++x) 
				blok[x] = 0;
				
			blok[i] = 1;
		
			res = min(res,dpek());
		}
	}
	
	printf("%d",res);


}