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

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define ALL(G) (G).begin(),(G).end()

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int INF = 1000000009;
const int MAXN = 300;

int n, m, k, ans = INF;
int dp[MAXN + 3];
vector<int> graph[MAXN + 3];
bool memo2[MAXN + 3][MAXN + 3];
bool memo3[MAXN + 3][MAXN + 3][MAXN + 3];
bool vis[MAXN + 3];
int del[10];

void Dfs(int v){
    dp[v] = 1;
    for(auto u : graph[v]){
        if(dp[u] == 0 && !vis[u])
            Dfs(u);
        dp[v] = max(dp[v], dp[u] + 1);
    }
}

int Check(){
    for(int i=1; i<=n; i++) dp[i] = 0;
    for(int i=1; i<=n; i++)
        if(dp[i] == 0 && !vis[i])
            Dfs(i);
            
    int res = 0;
    for(int i=1; i<=n; i++)
        res = max(dp[i], res);
    
    return res;
}

VI GetCand(){
    VI ret;
    int res = Check();
    int ind = -1;
    for(int i=1; i<=n; i++)
        if(dp[i] == res)
            ind = i;
    
    while(ind != -1){
        int ind2 = -1;
        for(auto u : graph[ind])
            if(dp[u] == dp[ind] - 1){
                ind2 = u;
                break;
            }
        ret.pb(ind);
        ind = ind2;
    }
    
    return ret;
}

void Solve(int cnt){
    if(cnt == 0){
        int res = Check();
        ans = min(res, ans);
        return;
    }
    
    
    if(k - cnt == 2 && memo2[del[k]][del[k-1]]) return;
    VI tmp;
    if(k - cnt == 3){
        tmp = vector<int>({del[k], del[k-1], del[k-2]});
        sort(tmp.begin(), tmp.end());
        if(memo3[tmp[0]][tmp[1]][tmp[2]])
            return;
    }
    
    vector<int> cand = GetCand();
    //printf("%d\n", cand.size());
    for(auto v : cand){
        vis[v] = true;
        del[cnt] = v;
        Solve(cnt-1);
        vis[v] = false;
    }
    
    if(k - cnt == 2){
        memo2[del[k]][del[k-1]] = memo2[del[k-1]][del[k]] = true;
    }
    
    if(k - cnt == 3){
        memo3[tmp[0]][tmp[1]][tmp[2]] = true;
    }
}

int main(){    
    scanf("%d %d %d", &n, &m, &k);
    for(int i=0; i<m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].pb(b);
    }
    
    Solve(k);
    printf("%d\n", ans);
    
    return 0;
}