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 <algorithm>
#include <iostream>
#include <vector>
using namespace std;

namespace {

constexpr int max_n = 333;

class Solver {
  vector<vector<int>> neigh;
  int k;

  int n;
  vector<char> ignore;

public:
  Solver(vector<vector<int>> const& neigh_, int k_):
    neigh(neigh_), k(k_), n(neigh.size()), ignore(n)
  {
  }

  int solve(int cur=0)
  {
    int len[max_n] = {};
    int from[max_n] = {};

    int longest = 0;
    for (int i = 0; i < n; ++i) {
      if (ignore[i]) continue;
      int l = 1;
      int f = -1;
      for (int j: neigh[i]) {
        if (ignore[j]) continue;
        if (l < len[j] + 1) {
          l = max(l, 1 + len[j]);
          f = j;
        }
      }
      len[i] = l;
      from[i] = f;
      longest = max(longest, l);
    }

    int res = longest;

    if (cur < k) {
      for (int i = 0; i < n; ++i) {
        if (ignore[i]) continue;
        if (len[i] < longest) continue;
        int c = i;
        while (c >= 0) {
          ignore[c] = true;
          res = min(res, solve(cur + 1));
          ignore[c] = false;
          c = from[c];
        }
        break;
      }
    }

    return res;
  }

  int operator()()
  {
    if (n <= k) return 0;
    return solve();
  }
};

}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, k;
  cin >> n >> m >> k;

  vector<vector<int>> neigh(n);

  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    neigh[y - 1].emplace_back(x - 1);
  }

  cout << Solver{neigh, k}() << endl;

  return 0;
}