//每个点拆为i,i+n，连一条边，容量为1，费用为0 
//若原图u到v有一条边，则新图里面u+n到v连一条边，容量为inf，费用为1 
//求最小费用最大流，要求每次的增广路费用小于等于k 
//最后得出的流量即为答案
//求好心人叉挂。。。 
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <deque>

using namespace std;

const int inf=10000000;

struct data
{
   int w;
   int next;
};

int n,m,t;
int cap[200][200],pay[200][200];//cap[][]容量，pay费用 
int p[200];//记录增广路径 
int d[300]; 
int f;
deque<data> q;
int s;//源点s=1+n，汇点为n 
bool vis[300];

int get()//找增广路 
{
    for(int i=1;i<=2*n;i++) d[i]=inf;
    d[s]=0;
    
    memset(vis,false,sizeof(vis));
    vis[s]=true;
    q.clear();
    data np={d[s],s};
    q.push_front(np);
    while(!q.empty())
    {
        int k=q.front().next;
        q.pop_front();
        for(int i=1;i<=2*n;i++)
          if(k!=i&&cap[k][i]>0&&d[k]+pay[k][i]<d[i])
          {
               d[i]=d[k]+pay[k][i];
               np.next=i;
               np.w=d[i];
               p[i]=k;
               if(!vis[i])
               {
                  vis[i]=true;
                  if(q.empty()||q.front().w>np.w) {q.push_front(np);}
                  else q.push_back(np);
               }
          }
    }
    
    return d[n];
}  
    

int main()
{
    while(scanf("%d%d%d",&n,&m,&t)==3)
    {
       if(n==0&&m==0&&t==0) break;
                                      
       memset(cap,0,sizeof(cap));
       for(int i=1;i<=n;i++)
          cap[i][i+n]=1;
       
       memset(pay,0,sizeof(pay));   
       for(int i=0;i<m;i++)
       {
          int x,y;
          scanf("%d%d",&x,&y);
          cap[x+n][y]=inf;
          pay[x+n][y]=1;
          pay[y][x+n]=-1;
       }
       
       s=1+n;
       int f=0;
       while(1)
       {
          int fee=get();
          if(fee>t) break;
          
          int tmp=inf;
          for(int u=n;u!=s;u=p[u])
              if(cap[p[u]][u]<tmp) tmp=cap[p[u]][u];
          
          f+=tmp;
          
          for(int u=n;u!=s;u=p[u])
          {
             cap[p[u]][u]-=tmp;
             cap[u][p[u]]+=tmp;
          }
       }
       
       printf("%d\n",f);
    }
}