#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <map>
#include <cmath>
#include <cstdlib>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <climits>
#include <ctype.h>
#include <utility>
using namespace std;
 
 
typedef long long ll;
 
const int N = 105,INF = 1e9;
vector<int> adj[N],vec[N],rvec[N];
vector<pair<int,int> > ed; 
int n, m, k, g[N][N], vis[N], par[N], qu[N], vs,from1[N],fromn[N],level[N],iter[N];
bool used[N];
 
struct edge {
    int to,cap,rev;
};
vector<edge> road[N];
void add_edge(int from,int to,int cap) {
    road[from].push_back((edge){to,cap,road[to].size()});
    road[to].push_back((edge){from,0,road[from].size()-1});
}
void bfs(int s) {
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()) {
        int v=que.front();que.pop();
        for(int i=0;i<road[v].size();i++) {
            edge &e=road[v][i];
            if (e.cap>0&&level[e.to]<0) {
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f) {
    if (v==t) return f;
    used[v]=1;
    for (int &i=iter[v];i<road[v].size();i++) {
        edge &e=road[v][i];
        if (e.cap>0&&level[v]<level[e.to]) {
            int d=dfs(e.to,t,min(f,e.cap));
            if (d>0) {
                e.cap-=d;
                road[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t) {
    int flow=0;
    for (;;) {
        bfs(s);
        if (level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0) flow+=f;
    }
}
void spfa(int source,int *dist,vector<int> e[N]) {
	queue<int> que;int in_que[N+1];
	memset(in_que,0,sizeof(in_que));
	fill(dist,dist+N+1,INF);
	que.push(source);dist[source]=0;
	while(!que.empty()) {
		int u=que.front();que.pop();
		in_que[u]=0;
		for (int i=0;i<e[u].size();i++) {
			int to=e[u][i];
			if (dist[u]+1<dist[to]) {
				dist[to]=dist[u]+1;
				if (!in_que[to]) {
					que.push(to);in_que[to]=1;
				}
			}
		}
	}
}
int main(int argc, char **argv) {
//	freopen("a", "r", stdin);
//	freopen("b", "w", stdout);
	while (scanf("%d%d%d", &n, &m, &k) && n) {
		ed.clear();
		for (int i = 0; i < n * 2; ++i) {
			adj[i].clear();vec[i].clear();rvec[i].clear();
			road[i].clear();
			from1[i]=fromn[i]=INF;
		}
		add_edge(0, n, 1e9);
		for (int i = 0; i < n; ++i)
			add_edge(i, i + n, 1);
		while (m--) {
			int u, v;
			scanf("%d%d", &u, &v);
			--u;
			--v;
			vec[u].push_back(v);
			rvec[v].push_back(u);
			ed.push_back(make_pair(u,v));
		}
		spfa(0,from1,vec);
		spfa(n-1,fromn,rvec);
		for (int i=0;i<ed.size();i++) {
			int u=ed[i].first,v=ed[i].second;
			if (from1[u]+fromn[v]+1<=k) add_edge(u + n, v, INF);
		}
		if (n == 1)
			printf("%d\n", m);
		else
			printf("%d\n", max_flow(0, n - 1));
	}
	return 0;
}