#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vll in, out;
ll k, ans=0;
vll need;
vvl g, g2;
vpl ran, chil;
void init(int n, int K) {
out = in = vll(n);k=K;
g2=g = vvl(n);
ran .pb( {k,-1});
chil.pb({-1,-1});
ran .pb( {0,k});
chil.pb({-1,-1});
}
void gin(ll i, ll v){
if(!need.empty() && need.back()==v)return;
if(ran[v].s<=ran[in[i]].s && chil[in[i]].f==-1)return;
in[i] = v;
if(in[i]==out[i]){
need.pb(v);
return;
}
if((ran[in[i]].s>ran[out[i]].s && in[i]!=0 && out[i]!=0) || (i<k && ran[v].f>=i)){
ans=1;
need.pb(v);
return;
}
for(ll j: g[i]){
gin(j, v);
if(!need.empty() && need.back()==v)return;
}
}
void gout(ll i, ll v){
if(!need.empty() && need.back()==v)return;
if(ran[v].f>=ran[out[i]].f && chil[out[i]].f==-1)return;
out[i] = v;
if(in[i]==out[i]){
need.pb(v);
return;
}
if((ran[in[i]].s>ran[out[i]].s && in[i]!=0 && out[i]!=0) || (i<k && ran[v].s<=i)){
ans=1;
need.pb(v);
return;
}
for(ll j: g2[i]){
gout(j, v);
if(!need.empty() && need.back()==v)return;
}
}
void check(){
if(ans==1)return;
while(!need.empty()){
ll o = need.back();
need.pop_back();
if(chil[o].f!=-1)continue;
ll l = ran[o].f, r=ran[o].s;
ll m = (l+r)/2;
if(l+1==r){ans=1;return;}
chil[o] = {ran.size(), ran.size()+1};
chil.pb({-1,-1});
chil.pb({-1,-1});
ran.pb({l,m});
ran.pb({m,r});
for(ll i = l; i < m; ++i){
for(ll j:g[i]){
gin(j,chil[o].f);
}
for(ll j:g2[i]){
gout(j,chil[o].f);
}
}
for(ll i = m; i < r; ++i){
for(ll j:g[i]){
gin(j,chil[o].s);
}
for(ll j:g2[i]){
gout(j,chil[o].s);
}
}
}
}
ll fin(ll x, ll i=1){
if(chil[i].f==-1)return i;
if(x<(ran[i].f+ran[i].s)/2)return fin(x, chil[i].f);
return fin(x, chil[i].s);
}
int add_teleporter(int u, int v) {
g[u].pb(v);
g2[v].pb(u);
if(u<k) gin(v, fin(u));
else gin(v, in[u]);
check();
if(ans==1)return ans;
if(v<k) gout(u, fin(v));
else gout(u, out[v]);
check();
return ans;
}
// 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;
// }
