// #ifdef LOCAL
// #include "grader.cpp"
// #endif
#include "game.h"
// void init(int n, int k);
// int add_teleporter(int u, int v);
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,sse4,bmi2,popcnt")
// #define int long long
#define iint signed
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)((x).size()))
#define SQ(x) ((x)*(x))
#define pii pair<int,int>
#define pipii pair<int,pii>
#define ppi pair<pii,int>
#define Graph vector<vector<int>>
#define Graphw vector<vector<pii>>
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define md(x) (((x)%(mod)+(mod))%(mod))
#define MD(x,M) (((x)%(M)+(M))%(M))
#define ld long double
#define pdd pair<ld,ld>
template<typename S> void chmin(S &x,S y) { x=min(x,y); }
template<typename S> void chmax(S &x,S y) { x=max(x,y); }
#define addmod(x,y) x=((x+(y))%mod)
#define Vi vector<int>
#define Vpii vector<pii>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) {cout<<(#x)<<":";for(auto allen:(x)) cout<<allen<<" ";cout<<" size="<<(x).size()<<endl;}
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& os,pair<T1,T2> p) { return os<<'{'<<p.f<<','<<p.s<<'}'; }
template<typename T1,typename T2>
istream& operator>>(istream& os,pair<T1,T2> &p) { return os>>p.f>>p.s; }
template<typename S>
ostream& operator<<(ostream& os,vector<S> p) { for(auto allen:p) os<<allen<<' ';return os<<'\n'; }
template<typename S>
istream& operator>>(istream& os,vector<S> &p) { for(auto &allen:p) os>>allen;return os; }
template<typename T1,typename T2>
pair<T1,T2> operator+(pair<T1,T2> p1,pair<T1,T2> p2) { return pair<T1,T2>(p1.f+p2.f,p1.s+p2.s); }
const int mod=998244353;
// const int maxn=1e5+5;
const int maxv=1e6+5;
const int inf=1ll<<60;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int rd(int l,int r) {
// return uniform_int_distribution<int>(l,r)(rng);
// }
#define i16 signed
#define Vi16 vector<i16>
const int maxn=30000+5;
namespace {
int n,k,eid;
vector<bitset<maxn>> r;
// vector<Vi16> it;
Graph g;
i16 it[1001][maxn];
};
void init(iint _n, iint _k) {
n=_n,k=_k;
r=vector<bitset<maxn>>(k);
eid=0;
g=Graph(n);
// it=vector<Vi16>(k,Vi16(n));
// REP(i,k-1) {
// g[i].pb(i+1);
// for(int j=i+1;j<k;j++) r[i][j]=1;
// }
REP(i,k-1)add_teleporter(i,i+1);
}
int __=0;
#define ___ {}//{if(__++%1000000==0) cerr<<__<<endl;}
iint add_teleporter(iint _u, iint _v) {
int x=_u,y=_v;
g[x].pb(y);
REP(i,k) {___
// vis[i].pb(0);
if((r[i][x]||i==x)&&!r[i][y]) {
// vis[i][eid]=1;
queue<int> q;
q.push(y);
it[i][x]++;
r[i][y]=1;
while(SZ(q)) {___
int u=q.front();
// op(i)ope(u)
q.pop();
for(;it[i][u]<SZ(g[u]);) {___
auto v=g[u][it[i][u]++];
if(r[i][v]) continue;
if(v==i) return 1;
q.push(v);
r[i][v]=1;
}
}
if(r[i][i]) return 1;
}
}
return 0;
}
#ifdef LOCAL
signed main() {
IOS();
freopen("4-08.in","r",stdin);
int n,m,k;
cin>>n>>m>>k;
init(n,k);
REP(i,m) {
int u,v;
cin>>u>>v;
if(add_teleporter(u,v)) {
cout<<i<<endl;
break;
}
}
return 0;
}
#endif
/*
*/
