#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<n;i++){
g[i].clear();
rg[i].clear();
}
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;
}
if((u>=k ? l[u]-1 : u)>=(v>=k ? r[v]+1 : v)){
return 1;
}
g[u].push_back(v);
rg[v].push_back(u);
queue<int>q;
if(v>=k&&(l[v]+r[v])/2<=(u>=k ? l[u]-1 : u)){
q.push(v);
}
if(u>=k&&(l[u]+r[u])/2>=(v>=k ? r[v]+1 : v)){
q.push(u);
}
while(!q.empty()){
int node = q.front();
q.pop();
while(1){
bool c = 0;
for(int i : g[node]){
int u = node;
int v = i;
if(u>=k&&(l[u]+r[u])/2>=(v>=k ? r[v]+1 : v)){
c=1;
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]>1){
return 1;
}
}
break;
}
}
if(c)
continue;
for(int i : rg[node]){
int u = i;
int v = node;
if(v>=k&&(l[v]+r[v])/2<=(u>=k ? l[u]-1 : u)){
c=1;
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]>1){
return 1;
}
}
break;
}
}
if(c)
continue;
break;
}
for(int i : g[node]){
if(i>=k&&(l[i]+r[i])/2<=l[node]-1){
q.push(i);
}
}
for(int i : rg[node]){
if(i>=k&&(l[i]+r[i])/2>=r[node]+1){
q.push(i);
}
}
if(l[node]-r[node]>1){
return 1;
}
}
return 0;
}
