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
// ten kod to masakra i spaghetti
// ale mam troche za duzo na glowie
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

int N, M, K;
int v, u;
int length = 301;
vector<int> best_r;
vector<int> graph[301];

int count[301];
bool removed[301];

int DFS(int x) {
  if(count[x] != -1)
    return count[x] + 1;
  count[x] = 0;

  int best_child = 0;
  for(auto u : graph[x])
    if(!removed[u])
      best_child = max(best_child, DFS(u));
  count[x] += best_child;

  return count[x] + 1;
}

void find_new_best() {
  for(int v = 1; v <= N; ++v)
    count[v] = -1;

  int l = 0;
  for(int v = 1; v <= N; ++v)
    if(count[v] == -1 && !removed[v])
      l = max(l, DFS(v));

  if(l < length)
    length = l;
}


int main() {
  ios_base::sync_with_stdio(NULL);
  cout.tie(NULL);
  cin.tie(NULL);


  cin >> N >> M >> K;

  // heh
  if(K == N) {
    cout << 0 << endl; 
    return 0;
  }


  for(int i = 0; i < M; ++i) {
    cin >> v >> u;
    graph[v].push_back(u);
  }

  find_new_best();
  if(K == 4) {
    for(int i = 1; i <= N; ++i) {
      for(int j = i + 1; j <= N; ++i) {
        for(int k = j + 1; k <= N; ++k) {
          for(int l = k + 1; l <= N; ++l) {
            removed[i] = true;        
            removed[j] = true;        
            removed[k] = true;        
            removed[l] = true;        

            find_new_best();

            removed[i] = false;        
            removed[j] = false;        
            removed[k] = false;        
            removed[l] = false;        
          } 
        } 
      }
    }
  } else if(K == 3) {
    for(int i = 1; i <= N; ++i) {
      for(int j = i + 1; j <= N; ++i) {
        for(int k = j + 1; k <= N; ++k) {
          removed[i] = true;        
          removed[j] = true;        
          removed[k] = true;        

          find_new_best();

          removed[i] = false;        
          removed[j] = false;        
          removed[k] = false;        
        }
      }
    }
  } else if(K == 2) {
    for(int i = 1; i <= N; ++i) {
      for(int j = i + 1; j <= N; ++i) {
        removed[i] = true;        
        removed[j] = true;        

        find_new_best();

        removed[i] = false;        
        removed[j] = false;        
      }
    }
  } else if(K == 1) {
    for(int i = 1; i <= N; ++i) {
      removed[i] = true;

      find_new_best();

      removed[i] = false;
    }
  }

  cout << length << endl;
  return 0;
}