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

const int N = 301;
int n, m, k, out=N;
int dist [N];
int from [N];
bool del [N];
vector <int> e [N];
vector <int> path [5];

void pleh (int k)
	{
	int w=0;
	for (int u=1; u<=n; u++)
		{
		dist[u]=1;
		from[u]=0;
		}
	for (int u=1; u<=n; u++)
		if (!del[u])
			{
			for (int v : e[u])
				if (dist[v]<dist[u]+1)
					{
					dist[v]=dist[u]+1;
					from[v]=u;
					}
			if (dist[u]>dist[w])
				w=u;
			}
	if (k==0)
		{
		out=min(out,dist[w]);
		return;
		}
	path[k].clear();
	path[k].push_back(w);
	for (w=from[w]; w!=0; w=from[w])
		path[k].push_back(w);
	for (int v : path[k])
		{
		del[v]=true;
		pleh(k-1);
		del[v]=false;
		}
	}

int main ()
	{
	scanf ("%d%d%d",&n,&m,&k);
	while (m--)
		{
		int a, b;
		scanf ("%d%d",&a,&b);
		e[a].push_back(b);
		}
	pleh(k);
	printf ("%d\n",out);
	return 0;
	}