#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN=3e5+7;
int in[MXN],out[MXN],p[MXN];//least out large in. if in > out return 1
int K;
int root(int u){
if(p[u]==u)return u;
return p[u]=root(p[u]);
}
bool done=0;
void unite(int u,int v){
int ru=root(u),rv=root(v);
if(ru==rv)return;
out[ru]=min(out[ru],out[rv]);
in[ru]=max(in[ru],in[rv]);
p[rv]=ru;
}
void init(int n, int k) {
K=k;
for(int i=0;i<n;++i){
p[i]=i;
in[i]=-1;
out[i]=INT_MAX;
}
}
int add_teleporter(int u, int v) {
if(done)return 1;
int ru=root(u),rv=root(v);
if(u<K&&v<K){
if(v<=u){
done=1;
return 1;
}
}
else if(v<K){
out[ru]=min(out[ru],v);
if(in[ru]>=out[ru]){
done=1;
return 1;
}
}
else if(u<K){
in[rv]=max(in[rv],u);
if(in[rv]>=out[rv]){
done=1;
return 1;
}
}
else{
unite(v,u);
if(in[rv]>=out[rv]){
done=1;
return 1;
}
}
return 0;
}
