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

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<bool> VB;
#define mp make_pair
#define pb push_back
#define st first
#define nd second

int cnt(int n, VI* adj, VB& blist) {
	VI dist(n, 1);
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (!blist[i]) {
			res = max(res, dist[i]);
			for (int u : adj[i]) {
				if (!blist[u]) {
					dist[u] = max(dist[u], dist[i] + 1);
				}
			}
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m, k, x, y;
	VI* adj;

	cin >> n >> m >> k;
	adj = new VI[n];

	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		adj[x - 1].pb(y - 1);
	}

	if (k == 0) {
		VB blist(n, false);
		cout << cnt(n, adj, blist);
		return 0;
	}

	int res = 1000000000;
	VI test(k, 0);

	for (int i = 0; i < (int)pow(n, k); i++) {
		VB blist(n, false);
		for (int u : test) blist[u] = true;

		res = min(res, cnt(n, adj, blist));

		auto it = test.begin();
		while (it < test.end() && *it == n - 1) {
			*it = 0;
			it++;
		}
		if (it != test.end()) *it = *it + 1;
	}

	cout << res;

	return 0;
}