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
111
112
113
114
115
116
117
118
119
120
121
122
// Author: Piotr Grzegorczyk (ud2@interia.eu)
// Task: PA2018/HER

#include <bits/stdc++.h>
using namespace std;

// TODO: wydajniejszy algorytm :(

vector<vector<int>> v_in, v_out;

vector<int> v_in_deg;
vector<int> v_out_deg;
vector<int> v_len;
vector<int> v_mark;
vector<bool> v_del;

int i_mark = 0;
int r_best = numeric_limits<int>::max();

int find(int k, int depth) {
	
	if (depth > r_best)
		return 0;

	if (v_mark[k] == i_mark)
		return v_len[k];

	int r = 1;
	for (int i=0; i<v_in[k].size(); i++) {
		int j = v_in[k][i];
		if (!v_del[j]) {
			r = max(r, 1 + find(j, depth+1));
		}
	}
	
	v_mark[k] = i_mark;
	v_len[k] = r;
	
	return r;
}

int find_max_length(int n) {

	i_mark++;
	
	int r = 0;
	for (int i=1; i<=n; i++)
		if (!v_del[i] && v_out_deg[i] == 0) {
			r = max(r, find(i, 1) );
			if (r > r_best)
				break;
		}

	if (r < r_best)
		r_best = r;
		
	return r;
}

void add(int k) {
	v_del[k] = false;	
	for (int i=0; i<v_out[k].size(); i++)
		v_in_deg[ v_out[k][i] ]++;
	for (int i=0; i<v_in[k].size(); i++)
		v_out_deg[ v_in[k][i] ]++;
}

void del(int k) {
	v_del[k] = true;	
	for (int i=0; i<v_out[k].size(); i++)
		v_in_deg[ v_out[k][i] ]--;
	for (int i=0; i<v_in[k].size(); i++)
		v_out_deg[ v_in[k][i] ]--;
}

void trace(int i, int k, int s, int n) {

	if (r_best==0)
		return;

	int r = find_max_length(n);

	for (int j=s; j<=n; j++) {
		if (i+1 <= k) {
			del(j);
			trace(i+1, k, j+1, n);
			add(j);
		}
	}
}

int main() {
	
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	
	v_in.resize(n+1);
	v_out.resize(n+1);
	
	v_len = vector<int>(n+1);
	v_mark = vector<int>(n+1, i_mark);	
	v_del = vector<bool>(n+1, false);	
	
	v_in_deg = vector<int>(n+1, 0);
	v_out_deg = vector<int>(n+1, 0);
	
	for (int i=0; i<m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		v_out[x].push_back(y);
		v_in[y].push_back(x);
	}

	for (int i=1; i<=n; i++)
		add(i);
	
	trace(0, k, 1, n);

	printf("%d\n", r_best);

	return 0;
}