#include <bits/stdc++.h>
using namespace std;
#include "game.h"
#define pii pair<int,int>
#define ff first
#define ss second
vector<set<int>> in,out;
vector<vector<int>> g,rev;
vector<int> par;
int n,k;
bool dobr(int cur,int m){
int p = par[cur];
if(p==-1)return true;
if(m>p)return out[p].count(cur)==1;
else return in[p].count(cur)==1;
}
bool dfs(int cur,int l,int r);
bool rfs(int cur,int l,int r);
bool addvertex(int x,int l,int r)
{
if(l>r)return 0;
int m=l+r>>1;
if(x==m)return 1;
int bad = 0;
for(int a:rev[x])
if(a==m||out[m].count(a))
{
bad=max<int>(bad,dfs(x,l,r));
break;
}
for(int a:g[x])
if(a==m||in[m].count(a))
{
bad=max<int>(bad,rfs(x,l,r));
break;
}
return bad;
}
bool dfs(int cur,int l,int r)
{
int m = l+r>>1;
if (cur == m || in[m].count(cur))
return 1;
if (out[m].count(cur) || !dobr(cur,m))
return 0;
out[m].insert(cur);
for (int a : g[cur])
if(dfs(a,l,r))return 1;
if(addvertex(cur,m+1,r))return 1;
return 0;
}
bool rfs(int cur,int l,int r)
{
int m = l+r>>1;
if (cur == m || out[m].count(cur))
return 1;
if (in[m].count(cur) || !dobr(cur,m))
return 0;
in[m].insert(cur);
for (int a : rev[cur])
if(rfs(a,l,r))return 1;
if(addvertex(cur,l,m-1))return 1;
return 0;
}
void init(int N,int K) {
n = N,k = K;
in.resize(k),out.resize(k);
g.resize(n),rev.resize(n);
par.resize(k,-1);
for(int i = 0; i < k-1; i++)
{
g[i].push_back(i+1);
rev[i+1].push_back(i);
}
function<void(int,int,int)> rec = [&](int l,int r,int pr)
{
if(l>=r)return;
int m = l+r>>1;
for(int i = m+1; i <= r; i++)
out[m].insert(i);
for(int i = l; i < m; i++)
in[m].insert(i);
par[m]=pr;
rec(l,m-1,m);
rec(m+1,r,m);
};
rec(0,k-1,-1);
}
bool add(int u,int v,int l,int r)
{
if(l>r)return 0;
int m = l+r>>1;
int ans = 0;
if(out[m].count(u)&&out[m].count(v))
return add(u,v,m+1,r);
if(in[m].count(u)&&in[m].count(v))
return add(u,v,l,m-1);
if((u==m||out[m].count(u)==1)&&out[m].count(v)==0)
ans=max<int>(ans,addvertex(v,l,r));
if((v==m||in[m].count(v)==1)&&in[m].count(u)==0)
ans=max<int>(ans,addvertex(u,l,r));
return ans;
}
int add_teleporter(int u, int v) {
if(u<k&&u==v)return 1;
g[u].push_back(v);
rev[v].push_back(u);
return add(u,v,0,k-1);
}
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int K = read_int();
std::vector<int> u(M), v(M);
for (int i = 0; i < M; ++i) {
u[i] = read_int();
v[i] = read_int();
}
init(N, K);
int i;
for (i = 0; i < M; ++i) {
int answer = add_teleporter(u[i], v[i]);
if (answer != 0 && answer != 1) {
i = -1;
break;
} else if (answer == 1) {
break;
}
}
printf("%d\n", i);
return 0;
}
