#include <bits/stdc++.h>
using namespace std;
/*
* You got a dream, you gotta protect it.
*/
typedef long long ll;
const int N = 100;
vector<int> adj[N];
int n, m, k, g[N][N], vis[N], par[N], qu[N], vs;
void addEdge(int u, int v, int c) {
if (!g[u][v] && !g[v][u]) {
adj[u].push_back(v);
adj[v].push_back(u);
}
g[u][v] += c;
}
bool BFS(int src, int sink) {
int s = 0, e = 0, lev = 0;
qu[e++] = src;
vis[src] = ++vs;
while (s < e && lev < k * 2) {
int siz = e - s;
while (siz--) {
int v = qu[s++];
for (size_t i = 0; i < adj[v].size(); ++i) {
int u = adj[v][i];
if (vis[u] == vs || !g[v][u])
continue;
vis[u] = vs;
par[u] = v;
qu[e++] = u;
if (u == sink)
return true;
}
}
++lev;
}
return false;
}
int maxFlow(int src, int sink) {
int flow = 0;
while (BFS(src, sink)) {
++flow;
for (int u = sink; u != src; u = par[u]) {
int v = par[u];
++g[u][v];
--g[v][u];
}
}
return flow;
}
int main(int argc, char **argv) {
// freopen("a", "r", stdin);
// freopen("b", "w", stdout);
while (scanf("%d%d%d", &n, &m, &k) && n) {
for (int i = 0; i < n * 2; ++i) {
adj[i].clear();
for (int j = i; j < n * 2; ++j)
g[i][j] = g[j][i] = 0;
}
addEdge(0, n, 1e9);
for (int i = 1; i < n; ++i)
addEdge(i, i + n, 1);
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
--u;
--v;
addEdge(u + n, v, 1);
}
if (n == 1)
printf("%d\n", m);
else
printf("%d\n", maxFlow(0, n - 1));
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovKgogKiBZb3UgZ290IGEgZHJlYW0sIHlvdSBnb3R0YSBwcm90ZWN0IGl0LgogKi8KCnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKY29uc3QgaW50IE4gPSAxMDA7CnZlY3RvcjxpbnQ+IGFkaltOXTsKaW50IG4sIG0sIGssIGdbTl1bTl0sIHZpc1tOXSwgcGFyW05dLCBxdVtOXSwgdnM7Cgp2b2lkIGFkZEVkZ2UoaW50IHUsIGludCB2LCBpbnQgYykgewoJaWYgKCFnW3VdW3ZdICYmICFnW3ZdW3VdKSB7CgkJYWRqW3VdLnB1c2hfYmFjayh2KTsKCQlhZGpbdl0ucHVzaF9iYWNrKHUpOwoJfQoJZ1t1XVt2XSArPSBjOwp9Cgpib29sIEJGUyhpbnQgc3JjLCBpbnQgc2luaykgewoJaW50IHMgPSAwLCBlID0gMCwgbGV2ID0gMDsKCXF1W2UrK10gPSBzcmM7Cgl2aXNbc3JjXSA9ICsrdnM7Cgl3aGlsZSAocyA8IGUgJiYgbGV2IDwgayAqIDIpIHsKCQlpbnQgc2l6ID0gZSAtIHM7CgkJd2hpbGUgKHNpei0tKSB7CgkJCWludCB2ID0gcXVbcysrXTsKCQkJZm9yIChzaXplX3QgaSA9IDA7IGkgPCBhZGpbdl0uc2l6ZSgpOyArK2kpIHsKCQkJCWludCB1ID0gYWRqW3ZdW2ldOwoJCQkJaWYgKHZpc1t1XSA9PSB2cyB8fCAhZ1t2XVt1XSkKCQkJCQljb250aW51ZTsKCQkJCXZpc1t1XSA9IHZzOwoJCQkJcGFyW3VdID0gdjsKCQkJCXF1W2UrK10gPSB1OwoJCQkJaWYgKHUgPT0gc2luaykKCQkJCQlyZXR1cm4gdHJ1ZTsKCQkJfQoJCX0KCQkrK2xldjsKCX0KCXJldHVybiBmYWxzZTsKfQoKaW50IG1heEZsb3coaW50IHNyYywgaW50IHNpbmspIHsKCWludCBmbG93ID0gMDsKCXdoaWxlIChCRlMoc3JjLCBzaW5rKSkgewoJCSsrZmxvdzsKCQlmb3IgKGludCB1ID0gc2luazsgdSAhPSBzcmM7IHUgPSBwYXJbdV0pIHsKCQkJaW50IHYgPSBwYXJbdV07CgkJCSsrZ1t1XVt2XTsKCQkJLS1nW3ZdW3VdOwoJCX0KCX0KCXJldHVybiBmbG93Owp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqKmFyZ3YpIHsKLy8JZnJlb3BlbigiYSIsICJyIiwgc3RkaW4pOwovLwlmcmVvcGVuKCJiIiwgInciLCBzdGRvdXQpOwoJd2hpbGUgKHNjYW5mKCIlZCVkJWQiLCAmbiwgJm0sICZrKSAmJiBuKSB7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuICogMjsgKytpKSB7CgkJCWFkaltpXS5jbGVhcigpOwoJCQlmb3IgKGludCBqID0gaTsgaiA8IG4gKiAyOyArK2opCgkJCQlnW2ldW2pdID0gZ1tqXVtpXSA9IDA7CgkJfQoJCWFkZEVkZ2UoMCwgbiwgMWU5KTsKCQlmb3IgKGludCBpID0gMTsgaSA8IG47ICsraSkKCQkJYWRkRWRnZShpLCBpICsgbiwgMSk7CgkJd2hpbGUgKG0tLSkgewoJCQlpbnQgdSwgdjsKCQkJc2NhbmYoIiVkJWQiLCAmdSwgJnYpOwoJCQktLXU7CgkJCS0tdjsKCQkJYWRkRWRnZSh1ICsgbiwgdiwgMSk7CgkJfQoJCWlmIChuID09IDEpCgkJCXByaW50ZigiJWRcbiIsIG0pOwoJCWVsc2UKCQkJcHJpbnRmKCIlZFxuIiwgbWF4RmxvdygwLCBuIC0gMSkpOwoJfQoJcmV0dXJuIDA7Cn0=