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
#pragma region Template 
#include <bits/stdc++.h> 

using namespace std;

#define For(i, n) for (int i = 0; i < (n); i++)
#define ForD(i, n) for (int i = (n) - 1; i >= 0; i--)
#define SORT(x) sort(begin(x), end(x))
#define REP(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#if DEBUG
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string>) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
#else
#define error(...) do {} while (0)
#endif

#define _upgrade do { ios::sync_with_stdio(0); cin.tie(0); } while (0)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#pragma endregion 

const int N = 420;
int in_deg[N];
int best = 1<<30;

int len[N];
int go_to[N];

vector<int> G[N];

bool removed[N];
int removed_cnt;

int n, k;

int dfs(int x) {
	if (len[x] != 0) return len[x];
	int longest = 0;

	for (int y : G[x]) {
		if (removed[y]) continue;

		int l = dfs(y);
		if (longest < l) {
			longest = l;
			go_to[x] = y;
		}
	}

	len[x] = longest + 1;
	return len[x];
}

void remove_longest() {
	For (i, n + 2) {
		len[i] = go_to[i] = 0;
	}

	int longest = 0;
	int which = 0;

	for (int i = 1; i <= n; i++) {
		if (!removed[i] && in_deg[i] == 0) {
			int l = dfs(i);
			if (longest < l) {
				which = i;
				longest = l;
			}
		}
	}
	
	if (removed_cnt == k) {
		best = min(best, longest);
		return;
	}

	vector<int> longest_path;
	int elem = which;
	while (elem != 0) {
		longest_path.push_back(elem);
		elem = go_to[elem];
	}

	for (int x : longest_path) {
		removed[x] = true;
		removed_cnt++;

		for (int y : G[x]) {
			in_deg[y]--;
		}

		remove_longest();
		
		removed[x] = false;
		removed_cnt--;
		for (int y : G[x]) {
			in_deg[y]++;
		}
	}
}

int main() {
    _upgrade;

	int m;
	cin >> n >> m >> k;
	For (i, m) {
		int a, b;
		cin >> a >> b;

		in_deg[b]++;
		G[a].push_back(b);
	}

	remove_longest();
	cout << best << "\n";
}