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
//
//  main.cpp
//  her
//
//  Created by Apple on 12/12/2018.
//  Copyright © 2018 Example. All rights reserved.
//

#include <cstdio>
#include <vector>
#include <stack>
#include <utility>

std::vector< std::pair<int, int> > wchodzace[307];
std::vector< std::pair<int, int> > wychodzace[307];
int n,m,k;

int ilewchodzi[307];
int najdluzszasciezka[307];

bool czybylo[307];

int policzile() {
    int i,l,j, mxall;
    mxall=0;
    std::stack<int> ktorewyzerowane;
    for (i=0; i<307; i++) {
        najdluzszasciezka[i]=1;
    }
    for (i=0; i<n; i++) {
        ilewchodzi[i]=0;
        for(j=0;j<wchodzace[i].size();j++) {
        //	if((wchodzace[i][j].first!=-1)!=(czybylo[i]==false))
		//	printf("WAZNE!!!")
          //  if(wchodzace[i][j].first!=-1) {
          	if(czybylo[i]==false && czybylo[wchodzace[i][j].first]==false) {
                ilewchodzi[i]++;
            }
        }
        if(ilewchodzi[i]==0 && czybylo[i]==false) {
            ktorewyzerowane.push(i);
        }
    }
    
    while (!ktorewyzerowane.empty()) {
        l=ktorewyzerowane.top();
        ktorewyzerowane.pop();
        if(najdluzszasciezka[l]>mxall) {
            mxall=najdluzszasciezka[l];
        }
        for (i=0; i<wychodzace[l].size();i++) {
            if(czybylo[wychodzace[l][i].first]==false && czybylo[l]==false) {
                ilewchodzi[wychodzace[l][i].first]--;
                if (ilewchodzi[wychodzace[l][i].first]==0) {
                    ktorewyzerowane.push(wychodzace[l][i].first);
                }
                if(najdluzszasciezka[wychodzace[l][i].first]<najdluzszasciezka[l]+1) {
                    najdluzszasciezka[wychodzace[l][i].first]=najdluzszasciezka[l]+1;
                    if(najdluzszasciezka[l]+1>mxall) {
                        mxall=najdluzszasciezka[l]+1;
                    }
                }
            }
        }
    }
    
    return mxall;
}


int rob(int kt, int k) {
    int i, odp, l;
    czybylo[kt]=true;
    
    
    if(k==0) {
        odp=policzile();
    } else {
        odp=-1;
        for (i=k-1; i<kt; i++) {
            if(czybylo[i]==false) {
                l=rob(i, k-1);
                if(odp==-1 || (l<odp && l!=-1)) {
                    odp=l;
                }
            }
        }
    }
    czybylo[kt]=false;
    return odp;
}


int main(int argc, const char * argv[]) {
    int l1,l2,i;
    scanf("%d%d%d",&n,&m,&k);
    for (i=0; i<m; i++) {
        scanf("%d%d",&l1,&l2);
        l1--;
        l2--;
        wchodzace[l2].push_back(std::make_pair(l1, wychodzace[l1].size()));
        wychodzace[l1].push_back(std::make_pair(l2, wchodzace[l2].size()-1));
    }
    printf("%d\n",rob(n, k));
    return 0;
}


/*
6 5 1
1 3
2 3
3 4
4 5
4 6
 
3 3 3
1 2
1 3
2 3
*/