#include<bits/stdc++.h>
#include "game.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
const int MX = 3e5+5;
const int LMX = 12e5+69;
vector<int> adj[2][MX];//0 is regular, 1 is reversed.
int K;
bool death;
set<int> God;
set<int> L[MX];
set<int> R[MX];
vector<int> collect;
void build(int id, int l, int r)
{
if(l > r)
return;
int m = (l+r)/2;
for(int i = l; i <= m; i++)
L[id].insert(i);
for(int i = m+1; i <= r; i++)
R[id].insert(i);
build(2*id, l, m);
build(2*id+1, m+1, r);
return;
}
int vis[MX];
void dfs(int s, int u, const set<int> &avoid, const set<int> &chop)
{
if(avoid.find(u) != avoid.end())
return;
if(chop.find(u) == chop.end())
return;
vis[u] = 1;
collect.pb(u);
for(int v: adj[s][u])
{
if(vis[v]) continue;
dfs(s, v, avoid, chop);
}
return;
}
void upd(int id, int l, int r, int u, int v, const set<int> &chop)
{
if(death) return;
bool uL = (L[id].find(u)==L[id].end())^1; bool vL = (L[id].find(v)==L[id].end())^1;
bool uR = (R[id].find(u)==R[id].end())^1; bool vR = (R[id].find(v)==R[id].end())^1;
bool uX = (!uL) && (!uR); bool vX = (!vL) && (!vR);
int m = (l+r)/2;
if(uR && vL)
{
death = true;
return;
}
//Check Left Recurse.
if(vL)
{
collect.clear();
dfs(1, u, L[id], chop);
for(auto s: collect)
{
vis[s] = 0;
L[id].insert(s);
}
upd(id, l, m, u, v, L[id]);
return;
}
//Check Right Recurse
if(uR)
{
collect.clear();
dfs(0, v, R[id], chop);
for(auto s: collect)
{
vis[s] = 0;
R[id].insert(s);
}
upd(id, l, m, u, v, R[id]);
return;
}
return;
}
void init(int n, int k)
{
K = k; death = false;
for(int i = 0; i < n; i++)
{
adj[0][i].clear();
adj[1][i].clear();
God.insert(i);
}
for(int i = 1; i < k; i++)
{
adj[0][i-1].pb(i);
adj[1][i].pb(i-1);
}
build(1, 0, k-1);
return;
}
int add_teleporter(int u, int v)
{
if(death) return death;
adj[0][u].pb(v);
adj[1][v].pb(u);
upd(1, 0, k-1, u, v, God);
return death;
}
