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

#ifdef LOCAL
template<class T, class U>
ostream& operator<<(ostream& os, pair<T, U> p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template<class C, class = typename C::value_type>
typename enable_if<!is_same<C, string>::value, ostream&>::type
operator<<(ostream& os, C c) {
    auto i = c.begin();
    while (i != c.end()) {
        os << " {"[i == c.begin()] << *i;
        os << ",}"[++i == c.end()];
    }
    return os;
}
#define debug(x) { cerr << #x << " = " << x << endl; }
#else
#define debug(...) {}
#endif

using graph = vector<vector<int>>;

vector<int> longest(int n, const graph &g, const vector<int> &erased) {
    vector<pair<int,int>> dp(n + 1);
    
    pair<int,int> maks = make_pair(0, 0);

    for (int i = 1; i <= n; i++) {
        if (!erased[i]) {
            maks = max(maks, make_pair(dp[i].first, i));

            for (int y : g[i]) {
                dp[y] = max(dp[y], make_pair(dp[i].first + 1, i));
            }
        }
    }
    
    vector<int> res;
    int cur = maks.second;

    while (cur != 0) {
        res.push_back(cur);
        cur = dp[cur].second;
    }

    return res;
}

int branching(int n, int k, const graph &g, vector<int> &erased) {
    vector<int> path = longest(n, g, erased);
//     debug(erased);
//     debug(path);

    if (k == 0) {
        return path.size();
    }
    
    int res = n;
    for (int v : path) {
        erased[v] = true;

        res = min(res, branching(n, k - 1, g, erased));
        
        erased[v] = false;
    }

    return res;
}

int solve(int n, int k, const graph &g) {
    vector<int> erased(n + 1);
    return branching(n, k, g, erased);
}

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

    int n, m, k;
    cin >> n >> m >> k;

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

    cout << solve(n, k, g) << "\n";
}