#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 3e5+5;
int n,k;
//l[i]-1 -> i is possible
//i -> r[i]+1 is possible
int l[mxn];
int r[mxn];
vector<int>g[mxn];
vector<int>rg[mxn];
void init(int N, int K) {
n=N;
k=K;
fill(l,l+n,-1);
fill(r,r+n,k);
for(int i = 0;i<k;i++){
l[i]=i;
r[i]=i;
}
for(int i = 0;i<k-1;i++){
g[i].push_back(i+1);
rg[i+1].push_back(i);
}
}
int add_teleporter(int u, int v) {
if(v<=u&&max(u,v)<k){
//cycle completely contained
return 1;
}
if(max(u,v)<k){
return 0;
}
g[u].push_back(v);
rg[v].push_back(u);
queue<int>qfrom;
if(v>=k&&(l[v]+r[v])/2<=(u>=k ? l[u]-1 : u)){
qfrom.push(v);
while((l[v]+r[v])/2<=(u>=k ? l[u]-1 : u)){
l[v]=(l[v]+r[v])/2+1;
if(l[v]>r[v]){
return 1;
}
}
}
queue<int>qto;
if(u>=k&&(l[u]+r[u])/2>=(v>=k ? r[v]+1 : v)){
qto.push(u);
while((l[u]+r[u])/2>=(v>=k ? r[v]+1 : v)){
r[u]=(l[u]+r[u])/2-1;
if(l[u]>r[u]){
return 1;
}
}
}
while(!qfrom.empty()){
int node = qfrom.front();
qfrom.pop();
assert(node>=k);
for(int i : g[node]){
if(i>=k&&(l[i]+r[i])/2<=l[node]-1){
qfrom.push(i);
while((l[i]+r[i])/2<=l[node]-1){
l[i]=(l[i]+r[i])/2+1;
if(l[i]>r[i]){
return 1;
}
}
}
}
if(l[node]>r[node]){
return 1;
}
}
while(!qto.empty()){
int node = qto.front();
qto.pop();
assert(node>=k);
for(int i : rg[node]){
if(i>=k&&(l[i]+r[i])/2>=r[node]+1){
qto.push(i);
while((l[i]+r[i])/2>=r[node]+1){
r[i]=(l[i]+r[i])/2-1;
if(l[i]>r[i]){
return 1;
}
}
}
}
if(l[node]>r[node]){
return 1;
}
}
return 0;
}
