#include <iostream>

#include <cstring>

#include <climits>

#include <cstdio>

#include <queue>

using namespace std;

#define min(x,y) (x)<(y)?(x):(y)

const int maxm = 10005;

const int maxn = 1100;

struct node{

    int v,flow,cost,next;

}edge[maxm];

int head[maxn],dis[maxn],vis[maxn],pre[maxn],cur[maxn];

int id,n,m,k;

int sink,source;

void add_edge(int u,int v,int flow,int cost){

    edge[id].v = v;edge[id].cost = cost;edge[id].flow = flow;edge[id].next = head[u];head[u] = id++;

    edge[id].v = u;edge[id].cost = -cost;edge[id].flow = 0  ;edge[id].next = head[v];head[v] = id++;

}

void init(){

    int u,v,i;

    source = 1,sink = n*2;

    memset(head,-1,sizeof(head));id = 0;

    for( i = 1; i <= m; i++){

        scanf("%d%d",&u,&v);

        add_edge(u+n,v,1,1);

    }

     for( i = 2; i < n; i++)//拆点

        add_edge(i,i+n,1,0);

    add_edge(1,n+1,5000000,0);

    add_edge(n,n+n,5000000,0);

}

int spfa(){

    memset(dis,-1,sizeof(dis));

    memset(vis,0,sizeof(vis));

    pre[source] = source;

    dis[source] = 0;

    vis[source] = 1;

    queue<int>que;

    que.push(source);

    while( !que.empty()){

        int u = que.front();

        que.pop();

        vis[u] = 0;

        for(int id = head[u]; id != -1; id = edge[id].next){

            int v = edge[id].v;

            if(edge[id].flow > 0 && (dis[v] == -1 || dis[v] > dis[u] + edge[id].cost )){

                dis[v] = dis[u] + edge[id].cost;

                pre[v] = u;cur[v] = id;

                if(!vis[v] ){

                    vis[v] =  1;

                    que.push(v);

                }

            }

        }

    }

    if(dis[sink] == -1 || dis[sink] > k)return 0;

    return 1;

}

int get_max(){

    int max_flow = 0;

    while(spfa())

    {

        //cout << dis[sink] << endl;

        max_flow += 1;

        int now = sink;

        while(now != source){

            edge[cur[now]].flow -= 1;

            edge[cur[now]^1].flow += 1;

            now = pre[now];

        }

    }

    return max_flow;

}

int main(){

    freopen("in.txt","r",stdin);

    while(~scanf("%d%d%d",&n,&m,&k),n||m||k){

        init();

        printf("%d\n",get_max());

    }

    return 0;

}