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

#define pb push_back

using namespace std;

template <class T> inline bool chkmin(T &a, T b){
	return a > b ? a = b, true : false;
}
template <class T> inline bool chkmax(T &a, T b){
	return a < b ? a = b, true : false;
}

const int N = 305, M = 405;

vector<int> adj[N], fwd[N];
bool ban[N];
int n, m, K, ans, fu[N], fd[N], len;

void solve(){
	memset(fu + 1, 0, sizeof(int) * n), memset(fd + 1, 0, sizeof(int) * n), len = 0;
	for (int u = 1; u <= n; ++u) if (!ban[u]) for (int v : fwd[u]) if (!ban[v]) chkmax(fu[u], fu[v] + 1);
	for (int u = n; u >= 1; --u) if (!ban[u]) for (int v : adj[u]) if (!ban[v]) chkmax(fd[u], fd[v] + 1);
	for (int u = 1; u <= n; ++u) if (!ban[u]) chkmax(len, fu[u] + fd[u]);
}

void getk1(){
	solve();
	vector<vector<pair<int, int>>> ranges(n + 1);
	for (int u = 1; u <= n; ++u) if (!ban[u]) for (int v : adj[u]) if (!ban[v]) ranges[fu[u] + fd[v] + 1].emplace_back(u, v);
	vector<int> dsu(n + 2);
	for (int u = 1; u <= n + 1; ++u) dsu[u] = u + (int)ban[u];
	function<int(int)> find = [&](int x){ return dsu[x] == x ? x : dsu[x] = find(dsu[x]); } ;
	vector<int> result(n + 1);
	for (int r = n; r >= 1; --r) {
		for (auto edge : ranges[r]) {
			for (int u = find(edge.first + 1); u < edge.second; u = find(dsu[u] = u + 1)) {
				result[u] = r;
			}
		}
	}
	for (int u = 1, c = 0; u <= n; ++u) if (!ban[u]) chkmax(result[u], c), chkmax(c, fu[u]);
	for (int u = n, c = 0; u >= 1; --u) if (!ban[u]) chkmax(result[u], c), chkmax(c, fd[u]);
	for (int u = 1; u <= n; ++u) if (!ban[u]) chkmin(ans, result[u]);
}

vector<int> cur;
set<vector<int>> visited;
void dfs(int pos){
	{
		vector<int> opt = cur;
		sort(opt.begin(), opt.end());
		if (visited.count(opt)) return;
		visited.insert(opt);
	}
	if (pos < K) {
		vector<int> road; int u;
		solve();
		for (u = 1; u <= n; ++u) if (!ban[u] && fd[u] == len) break;
		road.pb(u);
		while (true) {
			bool go = false;
			for (int v : adj[u]) if (!ban[v] && fd[v] + 1 == fd[u]) {
				road.pb(u = v);
				go = true;
				break;
			}
			if (!go) break;
		}
		for (int del : road) {
			ban[del] = true, cur.push_back(del); 
			dfs(pos + 1);
			ban[del] = false, cur.pop_back();
		}
	} else getk1();
}

int main(){
	int i, u, v;
	scanf("%d%d%d", &n, &m, &K);
	for (i = 1; i <= m; ++i) scanf("%d%d", &u, &v), adj[u].pb(v), fwd[v].pb(u);
	if (K >= n) puts("0");
	else if (!K) solve(), printf("%d\n", len + 1);
	else ans = n, dfs(1), printf("%d\n", ans + 1);
}