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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

int N,M,K;
std::vector<std::vector<int> > edges;
std::vector<std::vector<int> > edgesback;
std::map<std::vector<int>, int> cache;

int solve(std::vector<int> deleted) {
	int maxlevel = 1;
	int level[310];
	bool ignore[310];
	int visited[310];

	if (N == deleted.size()) {
		return 0;
	}

	if (cache.find(deleted) != cache.end()) {
		return cache[deleted];
	}

	for (int x=1; x<=N; x++) {
		ignore[x] = false;
		level[x] = 1;
		visited[x] = 0;
	}

	for (int d : deleted) {
		ignore[d] = true;
		level[d] = 0;
	}

	for (int x=1; x<=N; x++) {
		for (int y : edges[x]) {
			if (!ignore[x] && !ignore[y]) {
				level[y] = std::max(level[y], level[x]+1);
				maxlevel = std::max(maxlevel, level[y]);
			}
		}
	}

	if (deleted.size() == K) {
		cache[deleted] = maxlevel;
		return maxlevel;
	}

	//search max paths
	std::vector<int> maxpath;
	for (int v=1; v<=N; v++) {
		if (level[v] == maxlevel) {
			visited[v]=v;
			for (int x=N; x>=1; --x) {
				if (visited[x]==v) {
					for (int y : edgesback[x]) {
						if (level[y]+1==level[x] && !ignore[y]) {
							visited[y]=v;
						}
					}
				}
			}

			std::vector<int> path;
			for (int x=1; x<=N;x++) {
				if (visited[x]==v) {
					path.push_back(x);
				}
			}

			if (maxpath.empty() || path.size() < maxpath.size()) {
				maxpath = path;
			}
		}
	}

	//try delete one element
	int best = maxlevel;
	for (int x: maxpath) {
		std::vector<int> ndeleted = deleted;
		ndeleted.push_back(x);
		std::sort(ndeleted.begin(), ndeleted.end());
		best = std::min(best, solve(ndeleted));
	}

	cache[deleted] = best;
	return best;
}

int main() {
	scanf("%d %d %d",&N,&M,&K);
	edges.resize(N+1);
	edgesback.resize(N+1);

	for (int i=0; i<M; ++i) {
		int x,y;
		scanf("%d %d",&x,&y);
		edges[x].push_back(y);
		edgesback[y].push_back(x);
	}

	printf("%d\n",solve({}));
	return 0;
}