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

using namespace std;


int n, m, k, x, y;

vector<vector<int> > g;

vector<int> removed;

int best = std::numeric_limits<int>::max();

int longest = 0;

vector<bool>visited;

bool isRemoved(int v) {
    for(auto &el : removed) {
        if(el == v) return true;
    }
    return false;
}

void dfs(int v, int len) {
    longest = max(longest, len);
    for(auto &neigh : g[v]) {
        if(!visited[neigh] && !isRemoved(neigh)) dfs(neigh, len + 1);
    }

}

void getLongest() {
    longest = 0;
    visited = vector<bool>(n + 1, false);
    for(int i = 1; i <= n; i++) {
        if(!visited[i] && !isRemoved(i)) {
            dfs(i, 1);
        }
    }
    best = min(best, longest);
}



int main() {
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;

    g.resize(n + 1);

    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        g[x].push_back(y);
    }


    if(k > 0) {
        for (int a = 1; a <= n; a++) {
            if(k > 1) {
                for (int b = a + 1; b <= n; b++) {
                    if(k > 2) {
                        for (int c = b + 1; c <= n; c++) {
                            if(k > 3) {
                                for (int d = c + 1; d <= n; d++) {
                                    removed = {a, b, c, d};
                                    getLongest();
                                }
                            } else {
                                removed = {a, b, c};
                                getLongest();
                            }
                        }
                    } else {
                        removed = {a, b};
                        getLongest();
                    }
                }
            } else {
                removed = {a};
//                cout << a << endl;
//                cout << isRemoved(4) << endl;
                getLongest();
//                cout << longest << " " << best << endl;
            }
        }
    } else {
        removed = {};
        getLongest();
    }

    cout << best << endl;

    return 0;
}