#include <cstdio>
#include <vector>
std::vector<int> g[301];
bool del[301];
int ans(int n, int k) {
int dp[301] = {0};
bool con[301] = {0};
for(int i = n; i >= 0; i--)
if(!del[i])
for(auto j : g[i])
if(!del[j])
dp[i]= std::max(dp[i], dp[j]+1);
if(k == 0) return dp[0];
int ret = 1000;
for(auto j : g[0])
if(!del[j] && dp[0] == dp[j]+1)
con[j] = true;
for(int i = 1; i <= n; i++)
if(!del[i] && con[i]) {
del[i] = true;
ret = std::min(ret, ans(n, k-1));
del[i] = false;
for(auto j : g[i])
if(!del[j] && dp[i] == dp[j]+1)
con[j] = true;
}
return ret;
}
int main() {
int n, m, k;
scanf("%i%i%i", &n, &m, &k);
while(m--) {
int a, b;
scanf("%i%i", &a, &b);
g[a].push_back(b);
}
for(int i = 1; i <= n; i++)
g[0].push_back(i);
printf("%i", ans(n, k));
}