1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 500;
 5 struct arc{
 6     int to,flow,cost,next;
 7     arc(int x = 0,int y = 0,int z = 0,int nxt = -1){
 8         to = x;
 9         flow = y;
10         cost = z;
11         next = nxt;
12     }
13 }e[maxn*maxn];
14 int head[maxn],d[maxn],p[maxn],tot,S,T,n,m,k;
15 void add(int u,int v,int flow,int cost){
16     e[tot] = arc(v,flow,cost,head[u]);
17     head[u] = tot++;
18     e[tot] = arc(u,0,-cost,head[v]);
19     head[v] = tot++;
20 }
21 bool spfa(){
22     memset(d,0x3f,sizeof d);
23     memset(p,-1,sizeof p);
24     queue<int>q;
25     bool in[maxn] = {};
26     q.push(S);
27     d[S] = 0;
28     while(!q.empty()){
29         int u = q.front();
30         q.pop();
31         in[u] = false;
32         for(int i = head[u]; ~i; i = e[i].next){
33             if(e[i].flow && d[e[i].to] > d[u] + e[i].cost){
34                 d[e[i].to] = d[u] + e[i].cost;
35                 p[e[i].to] = i;
36                 if(!in[e[i].to]){
37                     in[e[i].to] = true;
38                     q.push(e[i].to);
39                 }
40             }
41         }
42     }
43     return p[T] > -1 && d[T] <= k;
44 }
45 int solve(int ret = 0){
46     while(spfa()){
47         int minF = INF;
48         for(int i = p[T]; ~i; i = p[e[i^1].to])
49             minF = min(minF,e[i].flow);
50         for(int i = p[T]; ~i; i = p[e[i^1].to]){
51             e[i].flow -= minF;
52             e[i^1].flow += minF;
53         }
54         ret += minF;
55     }
56     return ret;
57 }
58 int main(){
59     int u,v;
60     while(scanf("%d%d%d",&n,&m,&k) == 3 && (n||m||k)){
61         memset(head,-1,sizeof head);
62         tot = 0;
63         for(int i = 1; i <= n; ++i) add(i,i + n,1,0);
64         for(int i = 0; i < m; ++i){
65             scanf("%d%d",&u,&v);
66             add(u + n,v,INF,1);
67         }
68         S = 1 + n;
69         T = n;
70         printf("%d\n",solve());
71     }
72     return 0;
73 }