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
125
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define REP(x, n)  for(int x = 0; x < n; x++)
#define FOR(x, b, e) for (int x = (b); x <= (e); x++)
#define LL long long
#define ULL unsigned long long
#define MP std::make_pair
#define ST first
#define ND second
#define MAX 406

typedef std::pair<int, int> PII;
typedef std::vector<int> VI;


std::vector<PII>  deps;


int max_l[MAX];
int min_len;

//int arr[], int size

int compute_max_length(VI arr){
	std::vector<PII>::iterator it;
	REP(x, MAX){
		max_l[x]=1;
	}
	// int i=0;
	// REP(x, arr.size()){
		// printf("VEC %d\n", arr[x]);
	// }
	for (it = deps.begin() ; it != deps.end(); ++it){
		int st = (*it).ST;
		int nd = (*it).ND;
		bool exists = std::find(std::begin(arr), std::end(arr), st) != std::end(arr) || std::find(std::begin(arr), std::end(arr), nd) != std::end(arr);
		// i++;

		if (exists){
					// printf("ZZZZ% d %d\n", (*it).ST, (*it).ND);

			continue;
		}

		// printf("AAAA i%d %d %d\n", i, st, nd);
		max_l[nd] = std::max(max_l[nd], max_l[st]+1);
		max_l[0] = std::max(max_l[0], max_l[nd]);
	}
	// printf("MAX_L:\n");
	// REP(x, 7)
		// printf("%d ", max_l[x]);
	// printf("\n");

	return max_l[0];
}

void subset(int size, int left, int index, std::vector<int> &l){
    if(left==0){
        min_len = std::min(min_len, compute_max_length(l));
        return;
    }
    for(int i=index; i<=size;i++){
        l.push_back(i);
        subset(size,left-1,i+1,l);
        l.pop_back();
    }
}  

  // int array[5]={1,2,3,4,5};
  //   list<int> lt;   
  //   subset(array,5,3,0,lt);

// int gen(VI vector){

	// while(vector[0] < m - vector.size()){
	// 	std::vector<char> v
	// }

	// return compute_max_length(vector);	
// }



int main() {
	int n,m,k,a,b;
	scanf("%d%d%d", &n, &m, &k);
	REP(x, m){
		scanf("%d%d", &a, &b);
		deps.push_back(MP(a,b));
	}
	sort(deps.begin(), deps.end()); 
	// REP(x,m){
		// printf("%d %d\n", deps[x].ST, deps[x].ND);
	// }
	VI vec;
	REP(x,k){
		vec.push_back(x);
		// printf("VEC %d\n", vec[x]);

	}
	VI lt;
	min_len = compute_max_length(lt);
	if(k == 0){
		printf("%d\n", min_len);
		return 0;
	}
	if(k == n){
		printf("%d\n", 0);
		return 0;
	}
	if(n - k == 1){
		printf("%d\n", 1);
		return 0;
	}
	subset(n,k,1,lt);
	printf("%d\n", min_len);

	// int r =gen(vec);
	// REP(x,n+1){
		// printf("%d\n", max_l[x]);
	// }
	return 0;
}