#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
using namespace std;
const int MAXN=110,MAXM=5000,INF=1e9;
int n,m,lim; struct{ int u,v; } E[MAXM];
struct Dinic{
    static const int MAXN=5e4+10,MAXM=1e6+10;
    struct{ int v,f,nxt; } E[MAXM]; int head[MAXN],ec=1,st,ed;
    int cur[MAXN],dis[MAXN];
    void _add(int u,int v,int f){ E[++ec]={v,f,head[u]},head[u]=ec; }
    void add(int u,int v,int f){ _add(u,v,f),_add(v,u,0); }
    bool bfs(){
        memset(dis,-1,sizeof(dis));
        queue<int> que; que.push(st);
        while(que.size()){
            int u=que.front(); que.pop();
            for(int i=head[u];i;i=E[i].nxt){
                int v=E[i].v;
                if(E[i].f&&dis[v]<0) dis[v]=dis[u]+1,que.push(v);
            }
        }
        return dis[ed]>=0;
    }
    int dfs(int u,int flw){
        if(!flw||u==ed) return flw;
        int ret=0;
        for(int i=cur[u];i;cur[u]=i=E[i].nxt){
            int v=E[i].v;
            if(!E[i].f||dis[v]!=dis[u]+1) continue;
            int x=dfs(v,min(flw,E[i].f));
            if(!x) dis[v]=-1;
            flw-=x,ret+=x,E[i].f-=x,E[i^1].f+=x;
        }
        return ret;
    }
    int dinic(){
        int mxflow=0;
        while(bfs()){
            memcpy(cur,head,sizeof(head));
            mxflow+=dfs(st,INF);
        }
        return mxflow;
    }
    void dump_graph(){
        auto dump_id=[](int u){
            if(u==1) clog<<"st";
            else if(u==2) clog<<"ed";
            else{
                u-=2;
                if(u%2==1) clog<<"U[";
                else clog<<"V[";
                u/=2;
                clog<<u/(n*2)<<"]["<<u%(n*2)<<"]";
            }
        };
        RNG(u,1,n*n*4+10){
            for(int i=head[u];i;i=E[i].nxt) dump_id(u),clog<<"->",dump_id(E[i].v),clog<<" "<<E[i].f<<"\n";
        }
        clog<<endl;
    }
} G;
int nnd,U[MAXN][MAXN*2],V[MAXN][MAXN*2];
void ___(){ G.dump_graph(); }
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
#else
//  freopen("match.in","r",stdin);
//  freopen("match.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>lim;
    RNG(i,1,m) cin>>E[i].u>>E[i].v,E[i].u++,E[i].v++;
    int st=G.st=++nnd,ed=G.ed=++nnd;
    RNG(u,1,n){
        RNG(i,0,n*2-1) U[u][i]=++nnd,V[u][i]=++nnd;
    }
    G.add(st,U[1][0],INF);
    int sum=0;
    RNG(i,0,n*2-1){
        G.add(U[n][i],ed,INF);
        RNG(u,1,n) G.add(U[u][i],V[u][i],(u==1||u==n?INF:1));
        if(i>0){
            RNG(u,1,n) G.add(U[u][i-1],V[u][i],INF);
            RNG(ei,1,m) G.add(V[E[ei].u][i-1],U[E[ei].v][i],INF);
        }
        sum+=G.dinic();
        if(sum>lim){ cout<<i<<"\n"; break; }
    }
}