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
#include <bits/stdc++.h>
#define f first
#define s second
#define LL long long
#define ALL(V) V.begin(),V.end()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl "\n"
#define debug(x) cerr<<#x<<": "<<x<<endl
using namespace std;
const LL N=1e6+69, base=1024*1024,mod=1e9+7;
int wynik=2137;
vector <int> G[N], topo;
int dp[N], usu[N],n,m,k,wej[N];
void btrack(int k) {
    for(int i=1;i<=n;i++) dp[i]=-1;
    int ma=0;
    for(int i=0;i<n;i++) {
        int v=topo[i];
        dp[v]=0;
        if(usu[v]>0) continue;
        for(auto u:G[v]) {
            dp[v]=max(dp[v],dp[u]);
        }
        dp[v]++;
        ma=max(ma, dp[v]);
    }
    if(k==0) {
        wynik=min(wynik,ma);
        return;
    }
    int akt=0;
    for(int i=1;i<=n;i++) if(dp[i]==ma) akt=i;
    vector <int> vek;
    vek.push_back(akt);
    while(dp[akt]!=1) {
        for(auto u:G[akt]) {
            if(dp[u]+1==dp[akt]) {
                akt=u;
                break;
            }
        }
        vek.push_back(akt);
    }
    for(int i=0;i<vek.size();i++) {
        usu[vek[i]]++;
        btrack(k-1);
        usu[vek[i]]--;
    }
}
int32_t main(void) {
    boost;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++) {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        wej[b]++;
    }
    for(int huj=1;huj<=n;huj++) {
        for(int i=1;i<=n;i++) {
            if(wej[i]==0) {
                topo.push_back(i);
                wej[i]=-1;
                for(auto u:G[i]) wej[u]--;
            }
        }
    }
    reverse(ALL(topo));
//     for(int i=0;i<topo.size();i++) cout<<topo[i]<<" ";
//     return 0;
    btrack(k);
    cout<<wynik<<endl;
}