#include <bits/stdc++.h>
using namespace std;
const int MAX = 300;
vector<int> G[MAX];
bool del[MAX];
vector<int> L, P;
vector<int> C[5];
int n;
int solve(int k) {
L.assign(n, 1);
P.assign(n, -1);
for (int i = 0; i < n; i++) {
if (!del[i]) {
for (int u : G[i]) {
if (L[i] + 1 > L[u]) {
L[u] = L[i] + 1;
P[u] = i;
}
}
}
}
int res = 0;
int p = -1;
for (int i = 0; i < n; i++) {
if (!del[i] && L[i] > res) {
res = L[i];
p = i;
}
}
if (k == 0) {
return res;
}
C[k].clear();
while (p != -1) {
C[k].push_back(p);
p = P[p];
}
for (int u : C[k]) {
del[u] = true;
res = min(res, solve(k-1));
del[u] = false;
}
return res;
}
int main() {
int m, k;
scanf("%d %d %d", &n, &m, &k);
while (m--) {
int a, b;
scanf("%d %d", &a, &b);
G[a-1].push_back(b-1);
}
printf("%d\n", solve(k));
}