#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 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);
//Rewriting with inclusive bounds ie l[i] can reach i and i can reach r[i];
//if r[i]<=l[i] cycle found
queue<int>q;
if(v>=k&&((l[v]+r[v])/2)<=l[u]){
if(l[v]!=l[u]){
q.push(v);
inq[v]=1;
}
}
if(u>=k&&((l[u]+r[u])/2)>=r[v]){
if(r[v]!=r[u]){
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((l[node]+r[node])/2>=r[i]){
if(r[node]!=r[i]){
r[node]=r[i];
c=1;
}
}
}
for(int i : rg[node]){
//i -> node
//l[node] may be updated
if((l[node]+r[node])/2<=l[i]){
if(l[node]!=l[i]){
l[node]=l[i];
c=1;
}
}
}
if(c)
continue;
break;
}
if(r[node]<=l[node]){
return 1;
}
for(int i : g[node]){
if(!inq[i]&&i>=k&&(l[i]+r[i])/2<=l[node]){
if(l[node]!=l[i]){
q.push(i);
inq[i]=1;
}
}
}
for(int i : rg[node]){
if(!inq[i]&&i>=k&&(l[i]+r[i])/2>=r[node]){
if(r[node]!=r[i]){
q.push(i);
inq[i]=1;
}
}
}
}
return 0;
}
