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

const int MAX = 300;

vector<int> G[MAX];
bool del[MAX];
vector<int> L, P;
vector<int> C[5];

int n;

int solve(int k) {
  L.assign(n, 1);
  P.assign(n, -1);
  for (int i = 0; i < n; i++) {
    if (!del[i]) {
      for (int u : G[i]) {
        if (L[i] + 1 > L[u]) {
          L[u] = L[i] + 1;
          P[u] = i;
        }
      }
    }
  }
  int res = 0;
  int p = -1;
  for (int i = 0; i < n; i++) {
    if (!del[i] && L[i] > res) {
      res = L[i];
      p = i;
    }
  }
  if (k == 0) {
    return res;
  }
  C[k].clear();
  while (p != -1) {
    C[k].push_back(p);
    p = P[p];
  }

  for (int u : C[k]) {
    del[u] = true;
    res = min(res, solve(k-1));
    del[u] = false;
  }

  return res;
}

int main() {
  int m, k;
  scanf("%d %d %d", &n, &m, &k);
  while (m--) {
    int a, b;
    scanf("%d %d", &a, &b);
    G[a-1].push_back(b-1);
  }
  printf("%d\n", solve(k));
}