1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define  inf 100000000 7 using namespace std; 8 const int N=55; 9 const int E=20000;10 int dist[N],del[N][N],vis[N],head[N];11 bool visit[N];12 int n,m,k,cnt,ans,u,v,pre[N];13 struct Node{14   int v;15   int next;16 }edge[E];17 void init(){18  memset(head,-1,sizeof(head));19  memset(visit,0,sizeof(visit));20  memset(pre,0,sizeof(pre));21  cnt=0;22  ans=inf;23 }24 void add(int u,int v){25   edge[cnt].v=v;26   edge[cnt].next=head[u];27   head[u]=cnt++;28 }29 bool BFS(){30   for(int i=1;i<=n;i++){31     dist[i]=inf;32     vis[i]=false;33   }34       queue<int>Q;35       vis[1]=1;36       dist[1]=0;37       Q.push(1);38      while(!Q.empty()){39         int u=Q.front();40         Q.pop();41         vis[u]=0;42         for(int i=head[u];i!=-1;i=edge[i].next){43             int v=edge[i].v;44             if(!visit[v]&&dist[v]>dist[u]+1){45                 dist[v]=dist[u]+1;46                 pre[v]=u;47                 if(!vis[v]){48                     Q.push(v);49                     vis[v]=1;50                 }51                 if(v==n&&dist[v]<=k)return true;52             }53         }54      }55    return false;56 }57 void DFS(int depth){58     if(depth>=ans)return;59     memset(pre,0,sizeof(pre));60     if(!BFS()){61          ans=min(ans,depth);62          return;63     }64     int num=0;65     for(int i=pre[n];i!=1;i=pre[i]){66         del[depth][++num]=i;67     }68     for(int i=1;i<=num;i++){69         visit[del[depth][i]]=true;70         DFS(depth+1);71         visit[del[depth][i]]=false;72     }73 }74 75 int main(){76   while(~scanf("%d%d%d",&n,&m,&k)&&n){77      init();78      for(int i=1;i<=m;i++){79         scanf("%d%d",&u,&v);80         add(u,v);81      }82      DFS(0);83      printf("%d\n",ans);84   }85 }