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

using namespace std;

set < pair <int, int> > s;
set < pair <int, int> >::iterator sit;

vector <int> v[305];
vector <int>::iterator it;

int tab[305];
int syn[305];
int czy[305];

int n, m, k, x, y, dlugosc, numer, result;

bool funkcja (int K)
{
	dlugosc = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (czy[i] == 1)
		{
			tab[i] = 0;
			continue;
		}
		tab[i] = 1;
		syn[i] = 0;
		for (it = v[i].begin(); it != v[i].end(); ++it) if (tab[*it] + 1 > tab[i])
		{
			tab[i] = tab[*it] + 1;
			syn[i] = *it;
		}
		if (tab[i] > dlugosc)
		{
			dlugosc = tab[i];
			numer = i;
		}
	}
	if (K == 0)
	{
		if (dlugosc < result) result = dlugosc;
		return 0;
	}
	vector <int> w;
	w.push_back(numer);
	while (syn[numer] != 0)
	{
		numer = syn[numer];
		w.push_back(numer);
	}
	for (vector <int>::iterator vit = w.begin(); vit != w.end(); ++vit) if (czy[*vit] == 0)
	{
		czy[*vit] = 1;
		funkcja(K - 1);
		czy[*vit] = -1;
	}
	for (vector <int>::iterator vit = w.begin(); vit != w.end(); ++vit) czy[*vit] = 0;
	w.clear();
	return 0;
}

int main ()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; ++i)
	{
		scanf("%d%d", &x, &y);
		s.insert(make_pair(x, y));
	}
	for (sit = s.begin(); sit != s.end(); ++sit) v[sit->second].push_back(sit->first);
	for (int i = 1; i <= n; ++i)
	{
		tab[i] = 1;
		for (it = v[i].begin(); it != v[i].end(); ++it) if (tab[*it] + 1 > tab[i])
		{
			tab[i] = tab[*it] + 1;
			syn[i] = *it;
		}
		if (tab[i] > dlugosc)
		{
			dlugosc = tab[i];
			numer = i;
		}
	}
	if (k == 0)
	{
		printf("%d\n", dlugosc);
		return 0;
	}
	if (k == n)
	{
		printf("0\n");
		return 0;
	}
	result = 1000;
	funkcja(k);
	printf("%d\n", result);
	return 0;
}