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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

struct Graph {
    Graph(int n):edges(n){}
    void addEdge1(int a, int b) { edges[a].push_back(b); }
    int size() const { return (int)edges.size(); }
    Graph transpose() const {
        auto t = Graph(size());
        for (auto v=0; v<size(); ++v)
            for (auto u : edges[v])
                t.addEdge1(u, v);
        return t;
    }
    vector<vector<int>> edges;
};

Graph loadEdges(int n, int m) {
    auto g = Graph(n);
    for (auto i=0; i<m; ++i) {
        auto v = load<int>() - 1;
        auto u = load<int>() - 1;
        g.addEdge1(v, u);
    }
    return g;
}

int longestPath(const Graph& graph) {
    auto dyn = vector<int>(graph.size(), 1);
    for (auto v=0; v<graph.size(); ++v)
        for (auto u : graph.edges[v])
            dyn[u] = max(dyn[u], dyn[v] + 1);
    return *max_element(dyn.begin(), dyn.end());
}

template <typename T> struct SufMax {
    SufMax(const vector<T>& xs):sufr(xs){
        for (auto i=(int)xs.size()-2; i>=0; --i)
            sufr[i] = std::max(sufr[i+1], sufr[i]);
    }
    const T& max(int i) { return sufr[i]; }
    vector<T> sufr;
};

int solveK1(const vector<bool>& active, int n, const Graph& graph, const Graph& transposed) {
    auto dynleft = vector<int>(n, 1);
    for (auto v=0; v<n; ++v)
        if (active[v]) {
            for (auto u : graph.edges[v])
                if (active[u])
                    dynleft[u] = max(dynleft[u], dynleft[v] + 1);
        } else
            dynleft[v] = 0;
    auto dynright = vector<int>(n, 1);
    for (auto v=n-1; v>=0; --v)
        if (active[v]) {
            for (auto u : transposed.edges[v])
                if (active[u])
                    dynright[u] = max(dynright[u], dynright[v] + 1);
        } else
            dynright[v] = 0;
    auto onlyl = 0;
    auto onlyr = SufMax<int>(dynright);
    auto result = numeric_limits<int>::max();
    auto eque = priority_queue<pair<int, int>>(); // (path length, end vertex)
    for (auto v=0; v<n; ++v) {
        // remove edges from eque
        while (not eque.empty() and eque.top().second <= v)
            eque.pop();
        // calculate score
        auto score = max(eque.empty() ? 0 : eque.top().first, max(onlyl, v+1 < n ? onlyr.max(v+1) : 0));
        result = min(result, score);
        // update onlyl
        if (active[v])
            onlyl = max(onlyl, dynleft[v]);
        // add edges to eque
        if (active[v])
            for (auto u : graph.edges[v])
                if (active[u])
                    eque.emplace(dynleft[v] + dynright[u], u);
    }
    return result;
}

int recEliminate(int v0, vector<bool>& active, int n, int k, const Graph& graph, const Graph& transposed) {
    if (k == 1)
        return solveK1(active, n, graph, transposed);
    auto result = numeric_limits<int>::max();
    for (auto v=v0; v<n; ++v) {
        active[v] = false;
        result = min(result, recEliminate(v+1, active, n, k-1, graph, transposed));
        active[v] = true;
    }
    result = min(result, solveK1(active, n, graph, transposed));
    return result;
}

int solve(int n, int k, const Graph& graph) {
    if (k == 0)
        return longestPath(graph);
    auto transposed = graph.transpose();
    auto active = vector<bool>(n, true);
    return recEliminate(0, active, n, k, graph, transposed);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto n = load<int>();
    auto m = load<int>();
    auto k = load<int>();
    auto graph = loadEdges(n, m);
    auto answer = solve(n, k, graph);
    cout << answer << '\n';
}