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 <iostream>
#include <vector>

#define REP(x,n) for(int x=0;x<(n);++x)

using namespace std;

int n,m,k;
const int MAX_N = 301;
struct V {
	vector<int> e;
	int cycle;
};
V graph[MAX_N];

vector<int> excluded;

bool nextComb() {
	REP(x,k) {
		if(++excluded[x] != n-x) {
			REP(y,x)
				excluded[y] = excluded[x]+x-y;
			return true;
		}
	}
	return false;
}

bool inline isExcluded(int v) {
	for(const int& ex : excluded)
		if(ex==v)
			return true;
	return false;
}

int process(V& v) {
	v.cycle = 1;
	for(const int& e : v.e)
		if(!isExcluded(e)) {
			if(graph[e].cycle==0)
				process(graph[e]);
			v.cycle = max(v.cycle, 1+graph[e].cycle);
		}
}

int getCycle() {
	int maxi=0;
	REP(x,n)
		graph[x].cycle=0;
	REP(x,n) {
		if(isExcluded(x))
			continue;
//		for(auto ex : excluded) cout<<" "<<ex;
//		cerr<<" ex--> " << x << endl;
		V& v = graph[x];
		if(v.cycle==0) {
			process(v);
//			cerr << "maxi => " << max(maxi, v.cycle) << endl;
			maxi = max(maxi, v.cycle);
		}
	}
	return maxi;
}

int main() {
	n=7; k=4;
	cin>>n>>m>>k;
	int a,b;
	REP(x,m) {
		cin>>a>>b;
		graph[a-1].e.push_back(b-1);
	}
	excluded.resize(k);
	REP(x,k)
		excluded[x]=k-x-1;
	int mini = n+1, cur;
	do {
		cur = getCycle();
		mini = min(mini, cur);
//		for(auto x : excluded) cout<<" "<<x;
//		cerr<<" --> " << cur << endl;
	} while (nextComb());
	cout<<mini<<endl;
	return 0;
}