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
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto &i : a)
#define SZ(i) ((int)(i).size())
#define X first
#define Y second
#define PR std::pair
#define PII std::pair<int, int>
#define MP std::make_pair
#define ll long long
#define VI std::vector<int>

int best = 1000000000;
int n, m, k;
std::vector<VI> g;
VI right, ans;

int vec[4][350];
int plc[4];

void get_longest(int which, int v1=-1, int v2=-1, int v3=-1, int v4=-1){
	std::fill(right.begin(), right.end(), 0);
	for(int i = n-1; i >= 0; --i) if(i != v1 && i != v2 && i != v3 && i != v4)
		TRAV(ch, g[i]) if(ch != v1 && ch != v2 && ch != v3 && ch != v4)
			right[i] = std::max(right[i], right[ch]+1);
	VI ret;
	int max = 0;
	while(max == v1 || max == v2 || max == v3 || max == v4) max++;
	FOR(i, n) if(i != v1 && i != v2 && i != v3 && i != v4) if(right[i] > right[max]) max = i;
	plc[which] = 0;
	vec[which][plc[which]++] = max;
	while(right[vec[which][plc[which]-1]] > 0){
		TRAV(ch, g[vec[which][plc[which]-1]]) if(ch != v1 && ch != v2 && ch != v3 && ch != v4) if(right[ch] == right[vec[which][plc[which]-1]]-1){
			vec[which][plc[which]++] = ch;
			break;
		}
	}
}

void check(int v1=-1, int v2=-1, int v3=-1, int v4=-1){
	std::fill(ans.begin(), ans.end(), 1);
	int ret = 0;
	for(int i = n-1; i >= 0; --i){
		if(i != v1 && i != v2 && i != v3 && i != v4)
			TRAV(ch, g[i]) if(ch != v1 && ch != v2 && ch != v3 && ch != v4){
				ans[i] = std::max(ans[i], ans[ch]+1), ret = std::max(ret, ans[i]);
			}
	}
	best = std::min(best, ret);
}

int solve(){
	ans.resize(n);
	check();
	right.resize(n);
	if(n <= 50 || (n <= 60 && best > 31)){
		if(k == 4) FOR(v1, n) REP(v2, v1, n) REP(v3, v2, n) REP(v4, v3, n) check(v1, v2, v3, v4);
		else if(k == 3) FOR(v1, n) REP(v2, v1, n) REP(v3, v2, n) check(v1, v2, v3);
		else if(k == 2) FOR(v1, n) REP(v2, v1, n) check(v1, v2);
		else if(k == 1) FOR(v1, n) check(v1);
		else if(k == 0) check();
		return best;
	}
	if(k == 0){
		check();
		return best;
	}
	get_longest(0);
	FOR(p1, plc[0]){
		int v1 = vec[0][p1];
		if(k >= 2){
			get_longest(1, v1);
			FOR(p2, plc[1]){
				int v2 = vec[1][p2];
				if(k >= 3){
					get_longest(2, v1, v2);
					FOR(p3, plc[2]){
						int v3 = vec[2][p3];
						if(k >= 4){
							get_longest(3, v1, v2, v3);
							FOR(p4, plc[3]){
								int v4 = vec[3][p4];
								check(v1, v2, v3, v4);
							}
						}else{
							check(v1, v2, v3);
						}
					}
				}else{
					check(v1, v2);
				}
			}
		}else{
			check(v1);
		}
	}
	return best;
}


int main(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin >> n >> m >> k;
	g.resize(n);
	FOR(i, m){
		int a, b;
		std::cin >> a >> b;
		a--;b--;
		g[a].push_back(b);
	}
	std::cout << solve() << "\n";
	return 0;
}