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
#include <bits/stdc++.h>

using namespace std;

class heap_t {
 public:
  priority_queue<int> p, q;

  inline void push(int x) {
    p.push(x);
  }

  inline void pop(int x) {
    q.push(x);
  }

  inline int top() {
    while (!q.empty() && p.top() == q.top()) {
      p.pop();
      q.pop();
    }
    return p.top();
  }
};

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  vector<vector<int>> adj(n), rev(n);
  if (n == k) {
    puts("0");
    return 0;
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    adj[x].push_back(y);
    rev[y].push_back(x);
  }
  vector<bool> ban(n);
  vector<int> from(n), pre(n), to(n);
  auto init = [&]() {
    for (int i = 0; i < n; ++i) {
      if (ban[i]) {
        from[i] = to[i] = 0;
      } else {
        from[i] = to[i] = 1;
      }
      pre[i] = -1;
    }
    for (int i = 0; i < n; ++i) {
      if (!ban[i]) {
        for (auto j : adj[i]) {
          if (!ban[j]) {
            if (from[j] < from[i] + 1) {
              from[j] = from[i] + 1;
              pre[j] = i;
            }
          }
        }
      }
    }
    for (int i = n - 1; ~i; --i) {
      if (!ban[i]) {
        for (auto j : adj[i]) {
          if (!ban[j]) {
            to[i] = max(to[i], to[j] + 1);
          }
        }
      }
    }
  };
  if (!k) {
    init();
    printf("%d\n", *max_element(from.begin(), from.end()));
    return 0;
  }
  int answer = n;
  function<void(int)> dfs = [&](int current) {
    init();
    if (!current) {
      heap_t heap;
      int result = n;
      for (int i = 0; i < n; ++i) {
        if (!ban[i]) {
          heap.push(to[i]);
        }
      }
      for (int i = 0; i < n; ++i) {
        if (!ban[i]) {
          heap.pop(to[i]);
          for (auto j : rev[i]) {
            if (!ban[j]) {
              heap.pop(from[j] + to[i]);
            }
          }
          result = min(result, heap.top());
          for (auto j : adj[i]) {
            if (!ban[j]) {
              heap.push(from[i] + to[j]);
            }
          }
          heap.push(from[i]);
        }
      }
      answer = min(answer, result);
    } else {
      vector<int> chain;
      int x = max_element(from.begin(), from.end()) - from.begin();
      while (~x) {
        chain.push_back(x);
        x = pre[x];
      }
      for (auto x : chain) {
        ban[x] = true;
        dfs(current - 1);
        ban[x] = false;
      }
    }
  };
  dfs(k - 1);
  printf("%d\n", answer);
  return 0;
}