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

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

const int INF = 1000000009;
const LL LINF = 1000000000000000009LL;

#define FOR(i, b, e) for(int i = b; i <= e; ++i) 
#define FORD(i, b, e) for(int i = b; i >= e; --i) 
#define REP(i, n) FOR(i, 0, n-1)
#define REV(i, n) FORD(i, n-1, 0)
#define PB push_back
#define PP pop_back
#define MP make_pair
#define ST first
#define ND second
#define SIZE(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()

#define DEBUG(s) s

const int N = 305;

int n, m, k, a, b;
VI g[N];

int odw[N];
int dist[N];

int res = N;

void SubsetKLex(int k, int n, void (*fun) (VI &))
{	
	int i, p = k;
	VI A(k);
	REP(x, k) A[x] = x;
	
	if(k < n)
	{
		while(p)
		{
			fun(A);
			A[k-1] == n-1 ? p-- : p = k;
			if(p) FORD(i, k, p) A[i-1] = A[p-1] + i - p + 1;
		}
	}
	if(k == n)
	{
		res = 0;
	}
}

void solve(VI & v)
{
	//~ for(int i: v) cout<<i<<" ";
	//~ cout<<"\n";
	FOR(i, 1, n) odw[i] = 0;
	FOR(i, 1, n) dist[i] = 1;
	for(auto j: v) odw[j] = 1;
	
	FOR(i, 1, n)
	{
		if(!odw[i])
		{
			for(int j: g[i])
			{
				if(!odw[j])
				{
					dist[j] = max(dist[j], dist[i]+1);
				}
			}
		}
	}
	int wyn = 0;
	FOR(i, 1, n) wyn = max(wyn, dist[i]);
	res = min(res, wyn); 
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n>>m>>k;
	REP(i, m)
	{
		cin>>a>>b;
		g[a].PB(b);
	}	
	
	SubsetKLex(k, n, &solve);
	
	cout<<res<<"\n";
	
	return 0;
}