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
#include <stdio.h>
#include <stdlib.h>

#define MAXK 5
#define MAXN 310
#define MAXM 410

typedef struct {
  int f, t;
  int n;
} t_edge;

int ie = 0;
t_edge e[MAXM];
int f[MAXN];
int ir = 0;
int d[MAXN];
int revd[MAXN];
int out[MAXN];

int longestStart[MAXK][MAXN];
int longestEnd[MAXK][MAXN];

int xmax(int a, int b) {
  return (a>b) ? a : b;
}

int xmin(int a, int b) {
  return (a<b) ? a : b;
}

void go_dfs(int n) {
  if (d[n]!=-1)
    return ;
  int ix = f[n];
  while (ix!=-1) {
    go_dfs(e[ix].t);
    ix = e[ix].n;
  }
  d[n] = ir++;
}

void go_start(int k, int n) {
  if (out[n])
    return ;
  int ix = f[n];
  while (ix!=-1) {
    if (!out[e[ix].t])
      longestStart[k][n] = xmax(longestStart[k][n], 1+longestStart[k][e[ix].t]);
    ix = e[ix].n;
  }
}

void go_end(int k, int n) {
  if (out[n])
    return ;
  int ix = f[n];
  while (ix!=-1) {
    if (!out[e[ix].t])
      longestEnd[k][e[ix].t] = xmax(longestEnd[k][e[ix].t], 1+longestEnd[k][n]);
    ix = e[ix].n;
  }
}

int go(int k, int n) {
  int i, mm, v;
  int ex[MAXN];
  for (i=0;i<n;i++)
    longestStart[k][i] = longestEnd[k][i] = 0;
  for (i=0;i<n;i++)
    go_start(k, revd[i]);
  for (i=n-1;i>=0;i--)
    go_end(k, revd[i]);
  mm = 0;
  for (i=0;i<n;i++)
    if (!out[i])
      mm = xmax(mm, longestStart[k][i]+longestEnd[k][i]+1);
  if (k==0) {
    //printf("V=%d\n", mm);
    return mm;
  }
  for (i=0;i<n;i++)
    if (!out[i])
      ex[i] = (mm==longestStart[k][i]+longestEnd[k][i]+1);
  mm = -1;
  //printf("mm = %d\n", mm);
  for (i=0;i<n;i++)
    if (!out[i] && ex[i]) {
      out[i] = 1;
      v = go(k-1, n);
      if (mm==-1 || mm>v)
        mm = v;
      out[i] = 0;
    }
  return mm==-1 ? 0 : mm;
}

int main() {
  int n, m, k, i;
  scanf("%d%d%d", &n, &m, &k);
  for (i=0;i<n;i++) {
    f[i] = -1;
    out[i] = 0;
  }
  for (i=0;i<m;i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--;
    y--;
    e[ie].f = x;
    e[ie].t = y;
    e[ie].n = f[x];
    f[x] = ie;
    ie++;
  }
  for (i=0;i<n;i++)
    d[i] = -1;
  for (i=0;i<n;i++)
    go_dfs(i);
  for (i=0;i<n;i++)
    revd[d[i]] = i;
  printf("%d\n", go(k, n));
  return 0;
}