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

using namespace std;
typedef unsigned ui;

//PA2018
//Heros
//Spr wszystkie mozliwosci

vector<int> oute[300];
vector<int> ince[300];
int topsort[300],topc = 0;
char marked[300];
int curr,pom;
int w[300],n,m;

int longest_chain(){
   int res = 0;
   for(int i=0;i<n;i++){
      w[i] = 1;
   }
   for(int i=0;i<n;i++){
      curr = topsort[i];
      if(marked[curr])
         continue;
      for(ui j=0;j<ince[curr].size();j++){
         pom = ince[curr][j];
         if(!marked[pom] && w[pom]+1>w[curr])
            w[curr] = w[pom]+1;
      }
      if(w[curr]>res)
         res = w[curr];
   }
   return res;
}

int testuj(int k,int zacznijod){//do usuniecia
   int result, retval=10000000;
   if(k==0){
      return longest_chain();
   }else{
      for(int i=zacznijod;i<n;i++){
         if(!marked[i]){
            marked[i] = 1;
            result = testuj(k-1, i+1);
            if(result<retval)
               retval = result;
            marked[i] = 0;
         }
      }
   }
   return retval;
}


int main(){
   int k, u, v;//k do usuniecia
   int stos[300],sp = 0;
   int incc[300];
   scanf(" %d %d %d",&n,&m,&k);
   for(int i=0;i<n;i++){
      incc[i]=0;
      marked[i] = 0;
   }
   for(int i=0;i<m;i++){
      scanf(" %d %d", &u, &v);
      u--; v--;
      oute[u].push_back(v);
      ince[v].push_back(u);
      incc[v]++;
   }
   for(int i=0;i<n;i++){
      if(incc[i]==0)
         stos[sp++] = i;
   }
   while(sp>0){
      sp--;
      curr = stos[sp];
      topsort[topc++] = curr;
      for(ui i=0;i<oute[curr].size();i++){
         int ind = oute[curr][i];
         incc[ind]--;
         if(incc[ind]==0)
            stos[sp++] = ind;
      }
   }
   //for(int i=0;i<n;i++){
   //   printf("%d ",topsort[i]+1);
   //}
   printf("%d\n",testuj(k,0));
}