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

using namespace std;

int A[301][301], D[301][301];  
bool NOWY[301];
int WCH[301], WYCH[301], POPRZ[301], MAKSY[301];
vector<int> STOS[301],zerowe;
//set<pair <int, int> > kol;
int n,m, k;
void dfs(int v, int p)
{
//cout<<v<<" "; //do sledzenia dfs
NOWY[v]=false;
for(int i = 1;i<= n;i++)
    {
    int w=A[v][i];
    if(w == 1 && NOWY[i]) {
    	POPRZ[i] = v;
    	dfs(i,p);
	}
    }    
STOS[p].push_back(v);               
}                                                                  
          
int main()
{
ios_base::sync_with_stdio(0);
    int i, j , w1,w2,najd = 0, wierz,wyn = 300, dl;
    cin>>n>>m>>k;
	if(n - k  <= 1 ) {
		cout << 0; 
		return 0;
	}
    for(i=1;i<=m;++i) {
                          cin>>w1>>w2;
                          A[w1][w2] = 1;
                          WCH[w2]++;
                          WYCH[w1]++;
                          }     
    for(j=1;j<=n;++j) {
    	NOWY[j]=true;
		//kol.push(make_pair(-WCH[j],j))	;
	}
	//cout << kol.top().first <<" "<<kol.top().second << endl;
	for(j=1;j<=n;++j) {
		if(WCH[j]== 0)  {
			dfs(j,j);
			int temp = 0;	
			for(i = 0; i <= STOS[j].size(); i++) {
				w1 = STOS[j][i];
				D[j][POPRZ[w1]] = max(D[j][POPRZ[w1]],D[j][w1] + 1);
				if(D[j][POPRZ[w1]] > temp) temp = D[j][POPRZ[w1]];
				if(temp > najd) {
					najd = temp;
					wierz = j;
				}
			}
			//for(i = STOS[j].size()-1; i >= 0; i--) cout << STOS[j][i]<<" "; cout << endl;
			//for(i = STOS[j].size()-1; i >= 0; i--) cout << D[j][STOS[j][i]]<<" "; cout << endl;
			for(i=1;i<=n;++i) {
				NOWY[i]=true; POPRZ[i]=0;
			}
		}
	}
//cout <<"naj " <<najd << endl;
dl = najd + 1;	
while(dl > (najd + 1)/2){
	zerowe.resize(0);
	for(j=1;j<=n;++j)	{
		if (WCH[j] == 0) zerowe.push_back(j);
	}
	
	for(i = 0; i < zerowe.size(); i++){
		w1 = zerowe[i];
		WCH[w1]--;
		//cout <<" zer " << w1 << endl;
		for(j = 1; j <= n; j++) if(A[w1][j] > 0) WCH[j]--;
	}
	dl--;
	if(zerowe.size() <= k) wyn = min(wyn, dl - 1);		
}

cout << wyn;
    


return 0;
}