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
#include <stdio.h>
#include <vector>
#include<cmath>
std::vector<int> v[300];
std::vector<int> v2[300];
bool czyOut[300]={};
int t[4]={};
int n,m,k;
int fun(int * dropped, int size)
{
    int deg[300]={};
    int dist[300]={};
    int kol[300]={};
    int kolSize=0;
    for (int i =0;i<size;i++)
    {
	czyOut[dropped[i]]= true;
    }
    for (int i =0;i<n;i++)
    {
	if(czyOut[i]) continue;
	for (int j=0;j<v[i].size();j++)
	    deg[v[i][j]]++;
    }
    for (int i =0;i<n;i++)
	if(deg[i]== 0 && not czyOut[i])
	{
	    kol[kolSize++] = i;
	}
    int b=-1;

    int index=0;
    while(index <kolSize)
    {
	int u = kol[index];
	for (int i=0;i<v[u].size();i++)
	{
	    int cur = v[u][i];
	    if(czyOut[cur]) continue;
	    dist[cur] = std::max(dist[cur],dist[u]+1);
	    b=std::max(b, dist[cur]);
	    deg[cur]--;
	    if(deg[cur]==0)
		kol[kolSize++]=cur;
	}
	index++;
    }
    for (int i =0;i<size;i++)
    {
	czyOut[dropped[i]]= false;
    }
    return b+1;

}
int res = 5000;
void gen(int min , int iteration)
{
    if(iteration == k)
    {
	res = std::min(res, fun(t,k));
	return ;
    }
    for (int i =min;i<=n-k+iteration;i++)
    {
	t[iteration] = i;
	gen(i+1,iteration +1);
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i =0;i<m;i++)
    {
	int a,b;
	scanf("%d%d",&a,&b);
	a--;b--;
	v[a].push_back(b);
    }
    gen(0,0);
    printf("%d\n",res);
}