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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

constexpr int N = 300;
vector<int> g[N];
bool deleted[N];
int longest[5][N], parent[5][N];

void comp(int n, int idx) {
    for(int i=0;i<n;++i) {
        longest[idx][i] = 0;
        parent[idx][i] = -1;
        if(deleted[i])
            continue;   
        for(int u : g[i]) if(!deleted[u] && longest[idx][u] > longest[idx][i]) {
            longest[idx][i] = longest[idx][u];
            parent[idx][i] = u;
        }
        longest[idx][i]++;
    }
}

int get_best(int n, int k) {
    comp(n, k);
    if(k == 0) return *max_element(longest[k], longest[k] + n);
    int elem = max_element(longest[k], longest[k] + n) - longest[k];
    int ret = N;
    while(elem != -1) {
        deleted[elem] = true;
        ret = min(ret, get_best(n, k-1));
        deleted[elem] = false;
        elem = parent[k][elem];
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    while(m--) {
        int x,y;
        cin>>x>>y;
        --x; --y;
        g[y].push_back(x);
    }
    cout << get_best(n, k) << endl;
}