1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "algorithm"
  5 #include "vector"
  6 #include "queue"
  7 #include "cmath"
  8 #include "string"
  9 #include "cctype"
 10 #include "map"
 11 #include "iomanip"
 12 using namespace std;
 13 #define pb push_back
 14 #define mp make_pair
 15 #define fi first
 16 #define se second
 17 #define lc(x) (x << 1)
 18 #define rc(x) (x << 1 | 1)
 19 #define lowbit(x) (x & (-x))
 20 #define ll long long
 21 #define maxn 1050
 22 #define maxm 1000050
 23 const int inf = 1 << 30;
 24 int maz[55][55];
 25 int n, m, k;
 26 int s, t;
 27 int eh[maxn], low[maxn], dist[maxn], pre[maxn], cur[maxn], tot, cnt[maxn];
 28 
 29 struct Edge {
 30     int u, v, cap, flow, next;
 31 }et[maxm];
 32 
 33 void init() {
 34     tot = 0;
 35     memset(eh, -1, sizeof(eh));
 36 }
 37 
 38 void add(int u, int v, int cap, int flow) {
 39     Edge e = {u, v, cap, flow, eh[u]};
 40     et[tot] = e;
 41     eh[u] = tot++;
 42 }
 43 
 44 void addedge(int u, int v, int cap) {
 45     add(u, v, cap, 0), add(v, u, 0, 0);
 46 }
 47 
 48 void floyd() {
 49     for(int k = 1; k <= n; k++) {
 50         for(int i = 1; i <= n; i++) {
 51             for(int j = 1; j <= n; j++) {
 52                 if(maz[i][k] != inf && maz[k][j] != inf)
 53                     maz[i][j] = min(maz[i][j], maz[i][k] + maz[k][j]);
 54             }
 55         }
 56     }
 57 }
 58 
 59 int isap(int s, int t, int n){
 60     int u, v, now, flow = 0;
 61     memset(dist, 0, sizeof(dist)); 
 62     memset(low, 0, sizeof(low));
 63     memset(cnt, 0, sizeof(cnt));
 64     for(u = 0 ; u <= n ; u ++) cur[u] = eh[u];
 65     low[s] = inf, cnt[0] = n, u = s;
 66     while(dist[s] < n) {
 67         for(now = cur[u]; now != -1; now = et[now].next)
 68             if(et[now].cap - et[now].flow && dist[u] == dist[ v = et[now].v ] + 1 ) break;
 69         if(now != -1) {
 70             cur[u] = pre[v] = now;
 71             low[v] = min(et[now].cap - et[now].flow, low[u]);
 72             u = v;
 73             if(u == t) {
 74                 for(; u != s; u = et[pre[u]].u){
 75                     et[pre[u]].flow += low[t];
 76                     et[pre[u]^1].flow -= low[t];
 77                 }
 78                 flow += low[t]; low[s] = inf;
 79             }
 80         } else {
 81             if(--cnt[dist[u]] == 0) break;
 82             dist[u] = n, cur[u] = eh[u];
 83             for(now = eh[u]; now != -1; now = et[now].next)
 84                 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
 85                     dist[u] = dist[ et[now].v ] + 1;
 86             cnt[dist[u]]++;
 87             if(u != s) u = et[pre[u]].u;
 88         }
 89     }
 90     return flow;
 91 }
 92 
 93 int main() {
 94     int u, v;
 95     while(~scanf("%d%d%d", &n, &m, &k)) {
 96         if(!n) break;
 97         s = 1, t = n;
 98         init();
 99         for(int i = 0; i < 55; i++)
100             for(int j = 0; j < 55; j++)
101                 maz[i][j] = inf;
102         for(int i = 0; i < m; i++) {
103             scanf("%d%d", &u, &v);
104             maz[u][v] = 1;
105         }
106         floyd();
107         for(int i = 2; i < n; i++) {
108             if(maz[s][i] + maz[i][t] <= k) {
109                 addedge(i, i + n, 1);
110             }
111         }
112         for(int i = 1; i <= n; i++) {
113             for(int j = 1; j <= n; j++) {
114                 if(maz[i][j] == 1) addedge(i + n, j, inf);
115             }
116         }
117         int ans = isap(s + n, t, 2 * n - 2);
118         cout << ans << endl;
119     }
120     return 0;
121 }
122