#include <cstdio>#include <cstring>#include <queue>using namespace std;#define maxn 60#define maxm 50000int n,m,K,cnt,up;int head[maxn],pre[maxn];int road[maxn][maxn];bool del[maxn];queue<int> Q;bool flag;struct Edge{    int from,to,next;}e[maxm];void make(int from,int to){    e[cnt].from=from;    e[cnt].to=to;    e[cnt].next=head[from];    head[from]=cnt++;}void bfs(){    int i;    memset(pre,0,sizeof(pre));    pre[1]=-1;    Q.push(1);    while(!Q.empty())    {        int u=Q.front();Q.pop();        for(i=head[u];i!=-1;i=e[i].next)        {            if(del[e[i].to]==0&&pre[e[i].to]==0)            {                pre[e[i].to]=u;                Q.push(e[i].to);            }        }    }}void dfs(int x){    int i;    //if(flag==true) return ;    bfs();    if(pre[n]==0)    {        flag=true;        return ;    }    int num=0;    for(i=n;i!=-1;i=pre[i])    {        num++;        road[x][num]=i;    }    for(i=1;i<=num;i++)    if(num-1>K)    {        flag=true;        return;    }    if(x>up) return;    for(i=num-1;i>1;i--)    {        del[road[x][i]]=1;        dfs(x+1);        del[road[x][i]]=0;    }}int main(){    while(1)    {        int i,j,u,v;        scanf("%d%d%d",&n,&m,&K);        if(n==0) break;        cnt=0;        flag=0;        memset(head,-1,sizeof(head));        for(i=1;i<=m;i++)        {            scanf("%d%d",&u,&v);            make(u,v);        }        for(i=0;i<=n-2;i++)        {            up=i;            memset(del,0,sizeof(del));            dfs(1);            if(flag==true)                break;        }        printf("%d\n",up);    }    return 0;}