#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];
bool inq[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);
}
fill(inq,inq+n,0);
}
int div2(int a, int b){
return a/b-((a^b)<0&&(a%b));
}
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(l[u]>=r[v]){
return 1;
}
g[u].push_back(v);
rg[v].push_back(u);
//Rewriting with inclusive bounds ie l[i] can reach i and i can reach r[i];
//if r[i]<=l[i] cycle found
//l goes to mid+1 and r to mid always
queue<int>q;
if(v>=k&&div2((l[v]+r[v]),2)<l[u]){
q.push(v);
inq[v]=1;
}
if(u>=k&&div2(l[u]+r[u],2)>=r[v]){
q.push(u);
inq[u]=1;
}
while(!q.empty()){
int node = q.front();
q.pop();
inq[node]=0;
//update bounds of this
//i know it is updatable
while(1){
bool c = 0;
for(int i : g[node]){
//node -> i
//r[node] may be updated
if(div2((l[node]+r[node]),2)>=r[i]){
r[node]=div2((l[node]+r[node]),2);
c=1;
break;
}
}
if(r[node]<=l[node]){
return 1;
}
if(c)
continue;
for(int i : rg[node]){
//i -> node
//l[node] may be updated
if(div2((l[node]+r[node]),2)<l[i]){
assert(l[node]!=div2((l[node]+r[node]),2)+1);
l[node]=div2((l[node]+r[node]),2)+1;
c=1;
break;
}
}
if(r[node]<=l[node]){
return 1;
}
if(c)
continue;
break;
}
if(r[node]<=l[node]){
return 1;
}
for(int i : g[node]){
if(!inq[i]&&i>=k&&div2((l[i]+r[i]),2)<l[node]){
q.push(i);
inq[i]=1;
}
}
for(int i : rg[node]){
if(!inq[i]&&i>=k&&div2((l[i]+r[i]),2)>=r[node]){
q.push(i);
inq[i]=1;
}
}
}
return 0;
}
