#include <stdio.h>
#include <iostream>
#include <memory.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <math.h>
#include <stack>
#include <limits.h>
#include <iomanip>

using namespace std;
#define zero(x) memset(x,0,sizeof(x))
#define mone(x) memset(x,-1,sizeof(x))
#define ll long long
#define base 31
#define mod 1000000007
#define X first
#define Y second
#define fo(i,n) for(i=0;i<n;i++)
#define foo(i,n) for(i=1;i<=n;i++)
#define fa(i,I,n) for(i=I;i<n;i++)
#define sz(x) x.size()
#define pb push_back
const int inf=(1<<28);
int n,m,i,j,k,l,t,K;
namespace max_flow{
    const int M=300,oo=(1<<28);
    vector<int>g[M];
    //p[i][j] capacidad de la arista (i,j)
    //r[i][j] camino recidual
    int r[M][M],p[M][M],path[M];
    bool mar[M];
    void init(){
        zero(p);
        for(int i=0;i<M;i++)g[i].clear();
    }
    void add(int a,int b,int v){
        g[a].push_back(b);
        p[a][b]=v;
    }
    int bfs(int no,int nof){
        queue<int>q,q2;
        q.push(no);q2.push(oo);
        zero(mar);zero(path);
        mar[no]=1;
        path[nof]=path[no]=-1;
        while(!q.empty()){
            int nn=q.front(),pp=q2.front(),i;
            q.pop();q2.pop();
            fo(i,sz(g[nn])){
                int hi=g[nn][i],cc=p[nn][hi]-r[nn][hi];
                if(cc>0&&!mar[hi]){
                    mar[hi]=1;
                    path[hi]=nn;
                    if(hi==nof)return min(pp,cc);
                    q.push(hi);q2.push(min(pp,cc));
                }
            }
        }
        return 0;
    }
    int flow(int ini,int fin){
        int sol=0,val,po;zero(r);
        while(val=bfs(ini,fin)){
            sol+=val;
            po=fin;
            while(path[po]!=-1){
                r[path[po]][po]+=val;
                r[po][path[po]]-=val;
                po=path[po];
            }
        }
        return sol;
    }
}
int graph[55][55],paths[4005][2];
int main(){
    while(1){
        scanf("%d%d%d",&n,&m,&K);
        if(n+m+K==0)break;
        max_flow::init();
        fo(i,n)fo(j,n)graph[i][j]=(i==j?0:inf);//init floy
        fo(i,m){
            int u,v;
            scanf("%d%d",&u,&v);u--;v--;
            paths[i][0]=u;
            paths[i][1]=v;
            graph[u][v]=1;
        }
        fo(k,n)fo(i,n)fo(j,n)//floy
            graph[i][j]=min(graph[i][k]+graph[k][j],graph[i][j]);
        fo(i,n){
            max_flow::add(i,i+n,(i>0&&i<n-1?1:inf));
            max_flow::add(i+n,i,0);
        }
        fo(i,m){
            int u=paths[i][0],v=paths[i][1];
            if(u==v)continue;
            if(graph[0][u]+1+graph[v][n-1]<=K){
                max_flow::add(u+n,v,1);
                max_flow::add(v,u+n,0);
            }
        }
        printf("%d\n",max_flow::flow(0,n-1));
    }
    return 0;
}