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
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

#define MAX_VERTICES    310
#define MAX_K           5

int no_vertices;
vector<vector<int> > graph(MAX_VERTICES);
int deactivated[MAX_VERTICES];
int complexity[MAX_K][MAX_VERTICES];

void dfs_longest_path(int remaining_k,int vertice){
    int cplx=0;

    int edgescnt=0;

    for(int i=0;i<graph[vertice].size();i++){
        int edge=graph[vertice][i];

        if(deactivated[edge])
            continue;

        edgescnt++;

        if(complexity[remaining_k][edge]==0)
            dfs_longest_path(remaining_k,edge);

        if(complexity[remaining_k][edge]>cplx)
            cplx=complexity[remaining_k][edge];
    }

    if(edgescnt==0){
        complexity[remaining_k][vertice]=1;
        return;
    }

    complexity[remaining_k][vertice]=cplx+1;
}

vector<int> find_longest_path(int remaining_k){
    vector <int> res;
    for(int i=1;i<=no_vertices;i++)
        complexity[remaining_k][i]=0;

    for(int i=1;i<=no_vertices;i++){
        if(complexity[remaining_k][i])
            continue;

        if(deactivated[i])
            continue;

        dfs_longest_path(remaining_k,i);
    }

    //for(int i=1;i<=no_vertices;i++)
    //    cout<<i<<": "<<complexity[remaining_k][i]<<endl;

    int max_val=0,max_edge=0;

    for(int i=1;i<=no_vertices;i++){
        if(complexity[remaining_k][i]>max_val){
            max_val=complexity[remaining_k][i];
            max_edge=i;
        }
    }

    //now we have all complexities assigned and we know most complex vertice so we can start to generate max path
    if(max_val==0)
        return res;

    res.push_back(max_edge);

    while(--max_val){
        for(int i=0;i<graph[max_edge].size();i++){
            int e=graph[max_edge][i];

            if(complexity[remaining_k][e]==max_val){
                max_edge=e;
                res.push_back(max_edge);
                break;
            }
        }
    }

    return res;
}

int best_cplx=666666;

int remove_vertice_to_crete_esiest_path(int remaining_k){
    //return minimum obtained complexity
    vector <int> longest_path=find_longest_path(remaining_k);

    if(remaining_k==0){
        if(longest_path.size()<best_cplx){
            best_cplx=longest_path.size();

            /*cout<<"new best deactivation gives cplx: "<<best_cplx<<"\n";
            for(int i=1;i<=no_vertices;i++)
                if(deactivated[i])
                    cout<<i<<" ";
            cout<<endl;*/
        }

        return longest_path.size();
    }

    int cplx=INT_MAX;

    for(int i=0;i<longest_path.size();i++){
        int edge=longest_path[i];
        if(deactivated[edge])
            continue;

        deactivated[edge]=1;
        //cout<<"try on level "<<remaining_k<<" with deactivation of "<<edge<<endl;
        int cplx_new=remove_vertice_to_crete_esiest_path(remaining_k-1);
        deactivated[edge]=0;

        if(cplx_new<cplx)
            cplx=cplx_new;
    }

    return cplx;
}

int main(){
    int k;
    int no_edges;
    cin>>no_vertices>>no_edges>>k;

    for(int i=0;i<no_edges;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
    }


    //vector<int> longest_path=find_longest_path(k);
    //for(int i=0;i<longest_path.size();i++)
    //    cout<<longest_path[i]<<" ";

    int res=remove_vertice_to_crete_esiest_path(k);
    //cout<<"ANSWER: ";
    cout<<res;


    return 0;
}