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

using namespace std;

int res;
int n, m, k;
int dp[10000];
int czy_wchodzi[10000];
int gora[10000];
int min_res;

vector<int> drogi[10000];
vector<int> trans[10000];

void track( int pos=n, int wyn=min_res, int kk=k ) {
	int pom;
	while( pos ) {
		dp[pos] = 1;
		for( int i : drogi[pos] ) {
			dp[pos] = max( dp[pos], dp[i]+1 );
		}
		if( kk ) {
			if( !drogi[pos].empty() && (czy_wchodzi[pos] > 1 || dp[pos] > wyn) ) {
				pom = dp[pos];
				dp[pos] = 0;
				track( pos-1, wyn, kk-1 );
				dp[pos] = pom;
			} else if( drogi[pos].empty() && gora[pos] > wyn && czy_wchodzi[pos] > 1 ) {
				pom = dp[pos];
				dp[pos] = 0;
				track( pos-1, wyn, kk-1 );
				dp[pos] = pom;
			}
		}
		wyn = max( wyn, dp[pos] );
		if( wyn >= res ) return;
		if( (gora[pos]-kk)/(kk+1) >= res ) return;
		pos--;
	}
	res = min( res, wyn );
}

bool zabronione[10000];

void heura() {
	for( int i=0; i<100; i++ ) {
		for( int j=0; j<k; j++ ) {
			zabronione[ rand()%n+1 ] = 1;
		}
		int wyn=0;
		for( int j=n; j>0; j-- ) {
			if( zabronione[j] ) {
				zabronione[j] = 0;
				dp[j] = 0;
			} else {
				dp[j] = 1;
				for( int i : drogi[j] ) {
					dp[j] = max( dp[j], dp[i]+1 );
				}
				wyn = max( wyn, dp[j] );
			}
		}
		res = min( res, wyn );
	}
}

void policz_gora() {
	for( int i=1; i<=n; i++ ) {
		gora[i] = 1;
		for( int j : trans[i] ) {
			gora[i] = max( gora[i], gora[j]+1 );
		}
		min_res = max( min_res, (gora[i]-k)/(k+1) );
	}
}

int32_t main() {
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );

    cin >> n >> m >> k;
    srand( n+m-k );
    if( k>=n ) {
		cout << 0;
		return 0;
	}
    res = n+100;
    for( int a, b, i=1; i<=m; i++ ) {
        cin >> a >> b;
        drogi[a].push_back( b );
        trans[b].push_back( a );
		czy_wchodzi[b]++;
	}
    heura();
    policz_gora();
    track();
    cout << res << "\n";

    return 0;
}
//650 710 810 910 1160