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
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> t[301];
bool explored[301];
int length_to[301];
int parent[301];
bool red[301];
vector<int> topologicalOrder;
int n;

vector<int> path[5];
 void dfsUtil(int u) {
    explored[u] = true;
    for (int i = 0; i<t[u].size(); i++)
        if (!explored[t[u][i]] && red[t[u][i]]==false)
            dfsUtil(t[u][i]);
    topologicalOrder.push_back(u);
}

void dfs() {
    for (int u = 1; u <= n; u++)explored[u]=false;
    for (int u = 1; u <= n; u++)
        if (!explored[u] && red[u]==false)
            dfsUtil(u);
}

int find_path(int kk){
    dfs();
    for(int i = 1; i <=n; i++)length_to[i]=0;
    for(int i = n-1; i>=0;i--){
        int u = topologicalOrder[i];
        if(red[u])continue;
        for (int j = 0; j<t[u].size(); j++){
            if(red[t[u][j]])continue;
            if(length_to[t[u][j]]<=length_to[u]+1){
                length_to[t[u][j]]=length_to[u]+1;
                parent[t[u][j]]=u;
            }
        }
    }
    int maks = 0;
    int nr = 0;
    for(int i = 1; i <=n; i++){
        if(maks<length_to[i]){
            maks=length_to[i];
            nr=i;
        }
    }
    path[kk].clear();
    path[kk].push_back(nr);
    while(parent[nr]!=0){
        path[kk].push_back(parent[nr]);
        nr = parent[nr];
    }
    if(maks==0)return 0;
    return maks+1;
}


  
int main() {
    int m,k,x,y,minn=300;
   // cout<<"start!";
    cin>>n>>m>>k;
    for(int i =0;i<m;i++){
        cin>>x>>y;
        t[x].push_back(y);
    }
    if(k==0){
        cout<<find_path(0)<<"\n";
    }
    else if(k==1){
        find_path(0);
        for(int i = 0;i<path[0].size();i++){
            red[path[0][i]]=true;
            minn=min(minn,find_path(1));
            red[path[0][i]]=false;
        }
        cout<<minn<<"\n";
    }else if(k==2){
        find_path(0);
        for(int i0 = 0;i0<path[0].size();i0++){
            red[path[0][i0]]=true;
            find_path(1);
            for(int i1 = 0;i1<path[1].size();i1++){
                red[path[1][i1]]=true;
                minn=min(minn,find_path(2));
                red[path[1][i1]]=false;
            }
            red[path[0][i0]]=false;
        }
        cout<<minn<<"\n";
    }
    else if(k==3){
        find_path(0);
        for(int i0 = 0;i0<path[0].size();i0++){
            red[path[0][i0]]=true;
            find_path(1);
            for(int i1 = 0;i1<path[1].size();i1++){
                red[path[1][i1]]=true;
                find_path(2);
                for(int i2 = 0;i2<path[2].size();i2++){
                    red[path[2][i2]]=true;
                    minn=min(minn,find_path(3));
                    red[path[2][i2]]=false;
                }
                red[path[1][i1]]=false;
            }
            red[path[0][i0]]=false;
        }
        cout<<minn<<"\n";
    }else if(k==4){
        find_path(0);
        for(int i0 = 0;i0<path[0].size();i0++){
            red[path[0][i0]]=true;
            find_path(1);
            for(int i1 = 0;i1<path[1].size();i1++){
                red[path[1][i1]]=true;
                find_path(2);
                for(int i2 = 0;i2<path[2].size();i2++){
                    red[path[2][i2]]=true;
                    find_path(3);
                    for(int i3 = 0;i3<path[3].size();i3++){
                        red[path[3][i3]]=true;
                        minn=min(minn,find_path(4));
                        red[path[3][i3]]=false;
                    }
                    red[path[2][i2]]=false;
                }
                red[path[1][i1]]=false;
            }
            red[path[0][i0]]=false;
        }
        cout<<minn<<"\n";
    }
    return 0;
}