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
116
117
118
119
120
121
122
123
124
125
126
127
128
//Konrad Paluszek, University of Warsaw (former XIV LO Warsaw)
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#define sim template <class c
#define mor > muu & operator<< (
#define ris return *this
#define R22(r) sim> typename enable_if<1 r sizeof(dud<c>(0)), muu&>::type operator<<(c g) {
sim> struct rge {c h, n;};
sim> rge<c> range(c h, c n) {return rge<c>{h, n};}
sim, class F> struct rgm {c h, n; F f;};
sim, class F> rgm<c, F> map_range(c b, c e, F f) {return rgm<c, F>{b, e, f};}
sim, class F> rgm<typename c::const_iterator, F> map_range(const c &x, F f) {return map_range(x.begin(), x.end(), f);}
sim> auto dud(c *r) -> decltype(cerr << *r);
sim> char dud(...);
struct muu {
#ifdef LOCAL
	stringstream a;
	~muu() {cerr << a.str() << endl;}
	R22(<) a << boolalpha << g; ris;}
	R22(==) ris << range(begin(g), end(g));}
	sim mor rge<c> u) {
		a << '{';
		for (c s = u.h; s != u.n; ++s)
			*this << ", " + 2 * (s == u.h) << *s;
		ris << '}';
	}
	sim, class n mor pair <c,n> r) {ris << "(" << r.first << ", " << r.second << ")";}
	sim, class F mor rgm<c, F> u) {
		for (c s = u.h; s != u.n; ++s)
			u.f(*this << ", " + 2 * (s == u.h), *s);
		ris;
	}
	#else
	sim mor const c&) {ris;}
	#endif
	muu & operator()() {ris;}
};
#define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ")
#define imie(r) "[" #r ": " << (r) << "] "
#define imask(r) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] "
#define arr(a, i) "[" #a imie(i) ": " << a[i] << "] "
#define arr2(a, i, j) "[" #a imie(i) imie(j) << ": " << a[i][j] << "] "
sim> void mini(c &x, c y) {
	if (x > y)
		x = y;
}
sim> void maxi(c &x, c y) {
	if (x < y)
		x = y;
}
const int nax = 313;
int ans = nax;
vector <int> graf[nax];
int dp[nax];
bool banned[nax];
int n, m, k;
void rek(int left) {
	if (left == 0) {
		int curr = 0;
		for (int i = 1; i <= n; ++i) {
			if (banned[i])
				dp[i] = -1;
			else {
				dp[i] = 1;
				for (int x : graf[i])
					maxi(dp[i], dp[x] + 1);
				debug << arr(dp, i);
				maxi(curr, dp[i]);
				if (curr >= ans)
					return;
			}
		}
		debug << range(banned + 1, banned + n + 1) << imie(curr);
		mini(ans, curr);
		return;
	}
	vector <int> path;
	int wh = -1;
	for (int i = 1; i <= n; ++i) {
		if (banned[i])
			dp[i] = -1;
		else {
			dp[i] = 1;
			for (int x : graf[i])
				maxi(dp[i], dp[x] + 1);
			if (dp[i] >= ans) {
				wh = i;
				break;
			}
		}
	}
	if (wh == -1) {
		int curr = 0;
		for (int i = 1; i <= n; ++i) {
			maxi(curr, dp[i]);
			if (dp[i] == curr)
				wh = i;
		}
	}
	path.push_back(wh);
	while (dp[wh] > 1) {
		pair <int, int> best = {-1, -1};
		for (int x : graf[wh])
			maxi(best, {dp[x], x});
		wh = best.second;
		path.push_back(wh);
	}
	random_shuffle(path.begin(), path.end());
	debug << imie(left) imie(path);
	for (int del : path) {
		banned[del] = true;
		rek(left - 1);
		banned[del] = false;
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		graf[b].push_back(a);
	}
	rek(k);
	printf("%d\n", ans);
}