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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef pair <ii,int> iii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 405;

VI graf[N];
int res[N], a, b, n, m, k, i, j, ok[N], l, r, ind, nextt[N], result;

int get() {
	int r = 1;
	for (int i=n-1;i>=0;i--) {
		if (!ok[i]) continue;
		res[i] = 1;
		for (auto &w : graf[i]) if (ok[w]) res[i] = max(res[i], 1 + res[w]);
		r = max(r, res[i]);
	}
	return r;
}

int get2(int lim) {
	for (int i=n-1;i>=0;i--) {
		if (!ok[i]) continue;
		res[i] = 1;
		nextt[i] = -1;
		for (auto &w : graf[i]) if (ok[w]) {
			if (res[w] + 1 > res[i]) {
				nextt[i] = w;
				res[i] = res[w] + 1;
				if (res[i] > lim) {
					return i;
				}
			}
		}
	}
	return -1;
}

bool can(int ind, int kk, int last) {
	int r = get2(ind);
	if (r == -1) return true;
	if (kk == 0) return false;
	VI wek;
	wek.pb(r);
	while (nextt[r] != -1) {
		wek.pb(nextt[r]);
		r = nextt[r];
	}
	bool b;
	for (auto &w : wek) {
		ok[w] = 0;
		b = can(ind, kk - 1, w);
		ok[w] = 1;
		if (b) return true;
	}
	return false;
}

void go(int kk, int st) {
	if (kk == 0) {
		result = min(result, get());
		return;
	}
	for (int i=st;i<n - kk + 1;i++) {
		ok[i] = 0;
		go(kk - 1, i + 1);
		ok[i] = 1;
	}
}

int main() {
scanf("%d %d %d", &n, &m, &k);
for (i=0;i<n;i++) {
	graf[i].clear();
	ok[i] = 1;
}
while (m--) {
	scanf("%d %d", &a, &b);
	graf[a - 1].pb(b - 1);
}
if (n == k) {
	printf("0\n");
	return 0;
}
if (n == k + 1) {
	printf("1\n");
	return 0;
}
if (n <= 40) {
	result = INF;
	go(k, 0);
	printf("%d\n", result);
	return 0;
}
r = get();
if (k == 0) {
	printf("%d\n", r);
	return 0;
}
l = 1;
while (l < r) {
	ind = (l + r) / 2;
	//printf("%d\n", ind);
	if (can(ind, k, n)) r = ind; else l = ind + 1;
}
printf("%d\n", l);
return 0;
}