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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,m,k,al; //al - szukamy teraz, czy można wycisnąc długość najwyżej al
vector<vector<int>>Graf;
vector<bool>Disabled;
vector<int>pputV[5];
vector<int>pputO[5];


int K0case(){
	#define dp pputV[0]

	fill(dp.begin(), dp.end(), 1);
	int worst=0;
	for(int i=0;i<n;i++){
		worst = max(worst, dp[i]);
		for(int t : Graf[i])
			dp[t] = max(dp[t], dp[i]+1);
	}
	return worst;

	#undef dp
}

bool Recurse(int leftK){
	#define dpV pputV[leftK]
	#define dpO pputO[leftK]

	if(leftK==0){
		fill(dpV.begin(), dpV.end(), 1);
		for(int i=0;i<n;i++)
			if(!Disabled[i]){
				if(dpV[i]>al)
					return false;
				for(int t : Graf[i])
					dpV[t] = max(dpV[t], dpV[i]+1);
			}
		return true;
	}
	else{
		fill(dpV.begin(), dpV.end(), 1);
		fill(dpO.begin(), dpO.end(), -1);

		int found=-1;
		for(int i=0;i<n;i++)
			if(!Disabled[i]){
				if(dpV[i]>al){
					found=i;
					break;
				}
				for(int t : Graf[i])
					if(dpV[t] < dpV[i]+1){
						dpV[t] = dpV[i]+1;
						dpO[t] = i;
					}
			}

		if(found==-1)
			return true;

		do{
			Disabled[found]=true;
			if(Recurse(leftK-1))
				return true;
			Disabled[found]=false;
			found = dpO[found];
		}while(found!=-1);
	}

	return false;
	#undef dpV
	#undef dpO
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m >> k;
	Graf.clear();
	Graf.resize(n);
	for(int i=0;i<m;i++){
		int x,y;
		cin >> x >> y;
		Graf[x-1].push_back(y-1);
	}



	if(n<=42){
		//BRUTALNY ALGORYTM

		vector<bool>Skasowane(n, false);
		vector<int>pput(n);

		auto longest_path = [&]()->int{
			fill(pput.begin(), pput.end(), 1);
			int res=0;
			for(int i=0;i<n;i++)
				if(!Skasowane[i]){
					res=max(res, pput[i]);
					for(int x : Graf[i])
						pput[x]=max(pput[x], pput[i]+1);
				}
			return res;
		};

		for(int i=n-k;i<n;i++)
			Skasowane[i]=true;
		int result = 1000000000;
		do{
			result = min(result, longest_path());
		}while(next_permutation(Skasowane.begin(), Skasowane.end()));

		cout << result << "\n";
	}
	else{
		//LEPSZY ALGORYTM

		//prepare
		for(int i=0;i<=k;i++){
			pputV[i].resize(n);
			pputO[i].resize(n);
		}
		if(k==0){
			cout << K0case() << "\n";
			return 0;
		}
		Disabled = vector<bool>(n);

		//binsearch - najmniejsza możliwa maksymalna długość ścieżki jest w przedziale [a,b]
		int pntA=0, pntB=min(min(n,m+1), 35);
		while(pntA<pntB){
			int pntM = (pntA+pntB)/2;
			al=pntM;
			fill(Disabled.begin(), Disabled.end(), false);
			bool ans = Recurse(k); //czy można tak usunac, żeby zostawić najwyżej pntM-długie ścieżki?

			if(ans)
				pntB=pntM;
			else
				pntA=pntM+1;
		}

		cout << pntA << "\n";
	}
	return 0;
}