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

vector<vector<int>> G;
vector<bool> Vis;
vector<int> T, Val, Shuf;

void topo(int v){
    Vis[v] = true;
    for(int i=0; i<G[v].size(); i++){
        if(!Vis[G[v][i]])
            topo(G[v][i]);
    }
    T.push_back(v);
}

int main(){  
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    G.resize(n+1);
    for(int i=0; i<m; i++){
        int a, b; scanf("%d%d", &a, &b);
        G[a].push_back(b);
    }
    
    Vis.assign(n+1, false);
    for(int i=1; i<=n; i++){
        if(!Vis[i])
            topo(i);
    }

    for(int i=1; i<=n; i++)
        Shuf.push_back(i);
    
//     for(int i=0; i<n; i++)
//         printf("%d\n", T[i]);
    
    int best = 500;
    for(int i=0; i<100000; i++){
        random_shuffle(Shuf.begin(), Shuf.end());
        Val.assign(n+1, 1);
        
        for(int j=0; j<k; j++)
            Val[Shuf[j]] = 0;
        
        int tmp = 0;
        for(int j=0; j<n; j++){
            int tt = T[j];
            if(Val[tt] != 0){
                int ma = 0;
                for(int h=0; h<G[tt].size(); h++)
                    ma = max(ma, Val[G[tt][h]]);
                
                Val[tt] = ma+1;
            }
            tmp = max(tmp, Val[tt]);
        }
        
//         for(int j=1; j<=n; j++)
//             printf("%d ", Val[j]);
//         printf("\n");
        
        best = min(best, tmp);
    }
    
    printf("%d\n", best);
}