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

using namespace std;

const int N = 300 + 10;

vector <int> graf[N];
int zablokowany[N];
int stopnie[N];
vector <int> porzadek_topo;
pair <int,int> dp[N];

vector<int> znajdz_najdluzsza(int n) {
	int v;
	dp[0] = make_pair(0, -1);	
	for (int i = 1; i <= n; i++)
		dp[i] = make_pair(0, 0);

	for (int i = porzadek_topo.size() - 1; i >= 0; i--) {
		v = porzadek_topo[i];
		if (zablokowany[v])
			continue;

		dp[v] = make_pair(1, 0);
		for (int j = 0; j < graf[v].size(); j++) {
			if (zablokowany[graf[v][j]])
				continue;

			if (dp[v].first < dp[graf[v][j]].first + 1)
				dp[v] = make_pair(dp[graf[v][j]].first + 1, graf[v][j]);		
		}	
	}

	v = 0;
	for (int i = 1; i <= n; i++)
		if(!zablokowany[i] && dp[v].first < dp[i].first)
			v = i;

	vector <int> wynik;

	if (v == 0)
		return wynik;

	do{
		wynik.push_back(v);
		v = dp[v].second;
	}
	while (v != 0);
	return wynik;
}

int znajdz_najkrotsza(int n, int k) {
	vector <int> najdluzsza = znajdz_najdluzsza(n);
	int res = najdluzsza.size();
		
	if (k == 0)
		return najdluzsza.size();

	for (auto v : najdluzsza) {
		zablokowany[v] = 1;
		res = min(res, znajdz_najkrotsza(n, k-1));
		zablokowany[v] = 0;
	}
	return res;
}

void sortuj_top(int n) {
	int i, v;
	queue <int> kolejka;

	for (int i = 1; i <= n; i++)
		for(int j = 0; j < graf[i].size(); j++)
			stopnie[graf[i][j]]++;

	for (int i = 1; i <= n; i++)
		if (stopnie[i] == 0)
			kolejka.push(i);

	while (!kolejka.empty()) {
		v = kolejka.front();
		kolejka.pop();
		porzadek_topo.push_back(v);

		for (int i = 0; i < graf[v].size(); i++) {
			stopnie[graf[v][i]]--;
			if (stopnie[graf[v][i]] == 0)
				kolejka.push(graf[v][i]);		
		}	
	}
}

void wczytaj(int &n,int &m,int &k) {
	int v, u;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &v, &u);
		graf[v].push_back(u);
	}
}

int main() {
	int n, m, k;
	
	wczytaj(n, m, k);
	sortuj_top(n);
	
	printf("%d\n", znajdz_najkrotsza(n, k));
	
	return 0;
}