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
123
124
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mitte (lewy+prawy)/2
#define debug //
using namespace std;
typedef long long ll;
typedef long double ld;

vector <vector <int>  > revgraf;
vector <vector <int> > graf;
vector <int> topo;
vector <int> sto;
vector <bool> on;
vector <int> dp, rob;
vector <int> dp2;
vector <int> path;
int n, m, k;
void dfs (int a)
{
	topo.pb(a);
	sto[a]--;
	for (int s: graf[a])
	{
		
		sto[s]--;
		if (sto[s]==0) 
		{
			dfs(s);
		}
	}
}
int check (int a=0, int b=0, int c=0, int d=0)
{
	on[a]=on[b]=on[c]=on[d]=false;
	int ret=0;
	for (int v: topo) if (on[v])
	{
		dp[v]=1;
		for (int s: revgraf[v]) if (on[s])
		{
			dp[v]=max(dp[v], dp[s]+1);
		}
		ret=max(ret, dp[v]);
	}
	on[a]=on[b]=on[c]=on[d]=true;
	return ret;
}
set <int> wor;
priority_queue <pair <int, int> > kol;
int main ()
{
	scanf ("%d %d %d", &n, &m, &k);
	graf.resize(n+1);
	revgraf.resize(n+1);
	dp2.resize(n+1,1);
	dp.resize(n+1,1);
	sto.resize(n+1,0);
	on.resize(n+1,true);
	path.resize(n+1, -1);
	int a, b;
	rep(i,0,m)
	{
		scanf ("%d %d", &a, &b);
		graf[a].pb(b);
		sto[b]++;
		revgraf[b].pb(a);
	}
	rep(i,1,n+1) if (sto[i]==0)
	{
		dfs(i);
	}
	for (int v: topo)
	{
		dp[v]=1;
		for (int s: revgraf[v]) 
		{
			dp[v]=max(dp[v], dp[s]+1);
		}
	}
	reverse(topo.begin(), topo.end());
	for (int v: topo)
	{
		dp2[v]=1;
		for (int s: graf[v]) 
		{
			dp2[v]=max(dp2[v], dp2[s]+1);
		}
	}
	reverse(topo.begin(), topo.end());
	rep(i,1,n+1) path[i]=dp[i]+dp2[i];
	vector <int> tab;
	tab.resize(n);
	rep(i,0,n) tab[i]=i+1;
	sort(tab.begin(), tab.end(), [&path] (int a, int b) {return path[a]>path[b];});
	int x=40;
	if (m<=300) x+=3;
	if (m<=200) x+=3;
	if (m<=100) x+=3;
	for (int v: tab) if (x>0)
	{
		rob.pb(v);
		x--;
	}
	
	int res=check();
	if (k>=1) rep(a,0,(int)rob.size())
	{
		if (k>=2) rep(b,a+1,(int)rob.size())
		{
			if (k>=3) rep(c,b+1,(int)rob.size())
			{
				if (k>=4) rep(d,c+1,(int)rob.size()) res=min(res,check(tab[a],tab[b],tab[c],tab[d]));
				res=min(res,check(tab[a],tab[b],tab[c]));
			}
			res=min(res,check(tab[a],tab[b]));
		}
		res=min(res,check(tab[a]));
	}
	printf ("%d\n", res);
}