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
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
//#define cerr if(0)cout

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;

const int duzo = 769;
int n, m, st[duzo];
int nn = duzo;
vector<int> g[duzo], gt[duzo];
vector<int> wyje;
int dlug[duzo];

bool jest(int x) {
  for(auto y: wyje) if(x == y) return false;
  return true;
}

void usun() {
  for(auto w: wyje) for(auto x: g[w]) --st[x];
}

void napraw_stopnie() {
  for(int i = 1; i <= n; ++i) st[i] = gt[i].size();
}

int solve() {
  usun();
  queue<int> kol;
  for(int i = 1; i <= n; ++i) {
    if(st[i] == 0 && jest(i)) {
      kol.push(i);
    }
  }
  int ret = 0;
  while(!kol.empty()) {
    int ziom = kol.front();
    kol.pop();
    dlug[ziom] = 1;
    for(auto x: gt[ziom]) if(jest(x))
      dlug[ziom] = max(dlug[ziom], dlug[x] + 1);
    ret = max(ret, dlug[ziom]);
    for(auto x: g[ziom]) if(jest(x)) {
      --st[x];
      if(st[x] == 0) kol.push(x);
    }
  }
  napraw_stopnie();
  return ret;
}

void iteruj(int lev, int od) {
  if(lev == 0) {
    int rob = solve();
    nn = min(nn, solve());
    /*cerr << rob << ": ";
    for(auto x: wyje) cerr << x << " ";
    cerr << "\n";*/
    return;
  }
  for(int i = od; i <= n; ++i) {
    wyje.pb(i);
    iteruj(lev - 1, i + 1);
    wyje.pop_back();
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  // cin.tie(0);
  int k, u, v;
  cin >> n >> m >> k;
  for(int i = 1; i <= m; ++i) {
    cin >> u >> v;
    g[u].pb(v);
    gt[v].pb(u);
    ++st[v];
  }
  iteruj(k, 1);
  cout << nn;
  return 0;
}