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
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

const int NMAX=301;
const int MMAX=400;

using namespace std;

int nextv[NMAX];
pair<int,float> longest[NMAX];

struct graph {
   vector<int> G[NMAX];

   int n;
   int outdeg[NMAX];
   int indeg[NMAX];
   bool removed[NMAX];
   //vector<int> path;

   void initalize(int nn) {
       n=nn;
       fill(indeg, indeg+n+1, 0);
       fill(outdeg, outdeg+n+1, 0);
       fill(removed, removed+n+1, false);
   }

   void removeVertex(int v) {
       removed[v]=true;
   }

   void restoreVertex(int v) {
       removed[v]=false;
   }

   bool findLongPath(int t, vector<int> &path) {
       int v;
       for(v=n; v>=1; --v) {
           nextv[v]=0;
           longest[v]=make_pair(0,0.0);
           if(removed[v]) continue;
           for(auto w : G[v]) {
                    if(longest[v] < longest[w])
                    {
                        nextv[v]=w;
                        longest[v]=longest[w];
                    }

           }
           longest[v].first+=1;
           longest[v].second =
                   float(outdeg[v]+indeg[v])/longest[v].first
                   + longest[v].second*(longest[v].first-1)/longest[v].first;
           if(longest[v].first >= t)
               break;

       }
       path.clear();
       if(longest[v].first<t) return false;
       int i=0;
       while(i<t && v!=0) {
           path.push_back(v);
           v=nextv[v];
           ++i;
       }
       auto Lambda = [this] (int x, int y) -> bool
       {
          return indeg[x]+outdeg[y] > indeg[y]+outdeg[y];
       };
       sort(path.begin(), path.end(), Lambda);
       return true;
   }
} Gr;

bool killPaths(int ww,int t,int k) {
    if(ww!=0) Gr.removeVertex(ww);
    vector<int> path;
    if(!Gr.findLongPath(t,path)) {
        if(ww!=0) Gr.restoreVertex(ww);
        return true;
    }
    if(k==0) {
        if(ww!=0) Gr.restoreVertex(ww);
        return false;
    }
    for(auto w : path)
            if(killPaths(w,t,k-1)) {
                if(ww!=0) Gr.restoreVertex(ww);
                return true;
            }

    if(ww!=0) Gr.restoreVertex(ww);
    return false;
}

int main() {

   int n,m,k,x,y;

   scanf("%d %d %d",&n,&m,&k);
   if(k == n) {
       printf("%d\n",0);
       return 0;
   }
   Gr.initalize(n);

   for(int i=1; i<=m; ++i) {
       scanf("%d %d",&x,&y);
       Gr.G[x].push_back(y);
       Gr.indeg[y]++;
       Gr.outdeg[x]++;
   }

   int i=1; int j=n+1;
   while(i < j-1) {
       int s=(i+j)/2;
       if(killPaths(0,s,k)) j=s;
       else i=s;
   }
   printf("%d\n",i);
   return 0;
}