#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)
{
//cout << "Called!" << endl;
int m = (l+r)/2;
for(int i = l; i <= m; i++)
L[id].insert(i);
for(int i = m; i <= r; i++)
R[id].insert(i);
if(l==r)
return;
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)
{
//cout << "Updating " << l << " " << r << " for edge " << u << " " << v << endl;
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)
{
//cout << "There was a deadly cycle." << endl;
death = true;
return;
}
//Check Left Recurse.
if(vL)
{
collect.clear();
dfs(1, u, L[id], chop);
for(auto s: collect)
{
vis[s] = 0;
if(R[id].find(s) != R[id].end())
death = true;
L[id].insert(s);
}
//cout << "Left Recursing due to vertex v = " << v << " being in Left set " << endl;
if(l == r)
return;
upd(2*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;
if(L[id].find(s) != L[id].end())
death = true;
R[id].insert(s);
}
//cout << "Right Recursing due to vertex u = " << u << " being in Right set " << endl;
if(l == r)
return;
upd(2*id+1, m+1, r, u, v, R[id]);
return;
}
return;
}
void init(int n, int k)
{
K = k; death = false;
God.clear();
for(int i = 0; i < n; i++)
{
adj[0][i].clear();
adj[1][i].clear();
God.insert(i);
}
for(int i = 1; i <= (4*n+5); i++)
{
L[i].clear();
R[i].clear();
}
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;
}
vector<int> ncollect;
int nvis[MX];
void explore(int u)
{
nvis[u] = 1;
collect.pb(u);
for(int v: adj[0][u])
{
if(nvis[v]) continue;
explore(v);
}
return;
}
int pather(int u, int v)
{
explore(u);
int ret = nvis[v];
for(auto k: ncollect)
nvis[k] = 0;
ncollect.clear();
return nvis[v];
}
int add_teleporter(int u, int v)
{
if(death) return death;
if(u == v)
{
if(u < K)
return death = true;
else
return death;
}
adj[0][u].pb(v);
adj[1][v].pb(u);
upd(1, 0, K-1, u, v, God);
int okk = pather(v, u);
assert(death == pather(v, u));
return death = okk;
}
/*signed main()
{
int n, m, k;
cin >> n >> m >> k;
init(n, k);
vector<in> edge(m+1);
int pp = m+1;
for(int i = 1; i <= m; i++)
{
int x, y; cin >> x >> y;
if(add_teleporter(x, y))
pp = min(pp, i);
edge[i] = {x, y};
}
return 0;
}*/
