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

using namespace std;

int n, m, k;

vector<int> ein[310];
vector<int> eout[310];
vector<int> order;

vector<int> find_path(int e1, int e2, int e3, int e4) {
  int d[310], df[310];
  vector<int> path;

  for(int i = 0; i <= n; i++) {
    d[i] = 0;
    df[i] = 0;
  }

  for(int i = 1; i <= n; i++) {
    int max_d = 0;

    if(i != e1 && i != e2 && i != e3 && i != e4) {
      for(int j = 0; j < ein[i].size(); j++) {
        if(d[ein[i][j]] > max_d) {
          max_d = d[ein[i][j]];
          df[i] = ein[i][j];
        }
      }
      d[i] = max_d + 1;
    }
  }

  int m = 0, mi = 0;

  for(int i = 1; i <= n; i++) {
    if(d[i] > m) {
      m = d[i];
      mi = i;
    }
  }

  int c = mi;

  if(mi != 0) {
    path.push_back(mi);
  }

  while(df[c] >= 1) {
    c = df[c];
    path.push_back(c);
  }

  return path;
}

int main() {
  ios::sync_with_stdio(false);

  cin >> n >> m >> k;

  for(int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    eout[x].push_back(y);
    ein[y].push_back(x);
  }

  int k0 = 1000000000;
  int k1 = 1000000000;
  int k2 = 1000000000;
  int k3 = 1000000000;
  int k4 = 1000000000;

  vector<int> p1 = find_path(-1, -1, -1, -1);
  k0 = p1.size();

  for(int i1 = 0; i1 < p1.size(); i1++) {
    vector<int> p2 = find_path(p1[i1], -1, -1, -1);
    if(k1 > p2.size()) { k1 = p2.size(); }

    for(int i2 = 0; i2 < p2.size(); i2++) {
      vector<int> p3 = find_path(p1[i1], p2[i2], -1, -1);
      if(k2 > p3.size()) { k2 = p3.size(); }

      for(int i3 = 0; i3 < p3.size(); i3++) {
        vector<int> p4 = find_path(p1[i1], p2[i2], p3[i3], -1);
        if(k3 > p4.size()) { k3 = p4.size(); }

        for(int i4 = 0; i4 < p4.size(); i4++) {
          vector<int> p5 = find_path(p1[i1], p2[i2], p3[i3], p4[i4]);
          if(k4 > p5.size()) { k4 = p5.size(); }
        }
      }
    }
  }

  if(k == 0) { cout << k0; }
  if(k == 1) { cout << k1; }
  if(k == 2) { cout << k2; }
  if(k == 3) { cout << k3; }
  if(k == 4) { cout << k4; }

  return 0;
}