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
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 1000000;
int main() {
    vector < vector <int> > graf, pv;
    vector <int> t, p;
    int n, m, k, i, x, y, j, w, qn, ma, ca, nc, nw;
    cin >> n >> m >> k;
    bool* q = new bool[n];
    bool* s = new bool[n];
    int* d = new int[n];
    p.reserve(n);
    pv.reserve(k);
    t.reserve(n);
    graf.reserve(n);
    for(i = 0; i < n; i++) {
        graf.push_back(t);
    }
    for(i = 0; i < m; i++) {
        cin >> x >> y;
        x--;
        y--;
        graf.at(x).push_back(y);
    }
    for(ca = 0; ca < k; ca++) {
        w = 0;
        nc = 0;
        nw = 0;
        for(i = 0; i < n; i++) {
            p.clear();
            for(j = 0; j < n; j++) {
                q[j] = 1;
                s[j] = 0;
                p.push_back(-1);
                d[j] = M;
            }
            d[i] = 0;
            qn = n;
            while(qn) {
                ma = M;
                for(x = 0; x < n; x++) {
                    if(q[x] && (d[x] < ma)) {
                        ma = d[x];
                        y = x;
                    }
                }
                s[y] = 1;
                q[y] = 0;
                qn--;
                for(x = 0; x < graf.at(y).size(); x++) {
                    if(q[graf.at(y).at(x)] && (d[graf.at(y).at(x)] > (d[y] + 1))) {
                        d[graf.at(y).at(x)] = (d[y] + 1);
                        p.at(graf.at(y).at(x)) = y;
                    }
                }
            }
            pv.push_back(p);
            for(j = 0; j < n; j++) {
                if((d[j] > w) && (d[j] != M)) {
                    nc = i;
                    nw = j;
                    w = d[j];
                }
            }
        }
        j = 0;
        y = nw;
        if(w == 0) break;
        while(j <= (w/2)) {
            y = pv.at(nc).at(y);
            j++;
        }
        for(j = 0; j < graf.size(); j++) {
            for(x = 0; x < graf.at(j).size(); x++) {
                if(graf.at(j).at(x) == y) {
                    graf.at(j).erase(graf.at(j).begin() + x);
                }
            }
        }
        graf.at(y).clear();
    }
    w = 0;
    for(i = 0; i < graf.size(); i++) {
        for(j = 0; j < n; j++) {
            q[j] = 1;
            s[j] = 0;
            d[j] = M;
        }
        d[i] = 0;
        qn = n;
        while(qn) {
            ma = M;
            for(x = 0; x < n; x++) {
                if(q[x] && (d[x] < ma)) {
                    ma = d[x];
                    y = x;
                }
            }
            s[y] = 1;
            q[y] = 0;
            qn--;
            for(x = 0; x < graf.at(y).size(); x++) {
                if(q[graf.at(y).at(x)] && (d[graf.at(y).at(x)] > (d[y]+1))) {
                    d[graf.at(y).at(x)] = (d[y] + 1);
                }
            }
        }
        sort(d, d + n);
        for(j = (n-1); j >= 0; j--) {
            if(d[j] != M) {
                break;
            }
        }
        if(d[j] > w) {
            w = d[j];
        }
    }
    if(w > 0) {
        cout << w+1;
    }
    else {
        cout << w;
    }
    return 0;
}