#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb emplace_back
#define ff first
#define ss second
#define SZ(a) int(a.size())
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cerr << *l << " ", l++;
cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
#define lc 2 * id
#define rc 2 * id + 1
namespace {
int n, k;
vector<pii> seg;
vector<int> pos;
vector<vector<int>> g, rev;
vector<int> vst;
int query(int ql, int qr, int L = -1, int R = k, int id = 1) {
int M = L + (R - L) / 2;
if (L == R) return id;
if (ql <= M && M < qr) return id;
if (qr <= M) return query(ql, qr, L, M, lc);
else return query(ql, qr, M + 1, R, rc);
}
void push_node(int v, int l, int r) {
int id = pos[v];
l = max(l, seg[id].ff);
r = min(r, seg[id].ss);
pos[v] = query(l, r, seg[id].ff, seg[id].ss, id);
}
int get_come(int v) {
int id = pos[v];
if (seg[id].ff == seg[id].ss) return id;
return lc;
}
int get_go(int v) {
int id = pos[v];
if (seg[id].ff == seg[id].ss) return id;
return rc;
}
bool isAnc(int a, int b) {
return seg[a].ff <= seg[b].ff && seg[b].ss <= seg[a].ss;
}
void add_edge(int u, int v) {
g[u].pb(v);
rev[v].pb(u);
}
}
void init(int _n, int _k) {
n = _n;
k = _k;
seg.resize(4 * (k + 2));
pos.resize(n);
g.resize(n); rev.resize(n);
vst.resize(n);
for (int i = 0; i < k - 1; i++)
add_edge(i, i + 1);
auto build = [&](auto dfs, int l, int r, int id) -> void {
debug("build", l, r, id);
seg[id] = pii(l, r);
if (l == r) return;
int m = l + (r - l) / 2;
dfs(dfs, l, m, lc);
dfs(dfs, m + 1, r, rc);
};
build(build, -1, k, 1);
debug("ok");
for (int i = 0; i < n; i++) {
if (i < k) pos[i] = query(i, i);
else pos[i] = 1;
}
debug("init done");
}
int add_teleporter(int u, int v) {
debug("test", u, v);
add_edge(u, v);
int come = u, go = v;
bool flag = false;
auto comp_come = [&](int x, int y) {
x = get_come(x); y = get_come(y);
if (x == y) return false;
if (isAnc(x, y)) return false;
if (isAnc(y, x)) return true;
return !(seg[x].ss < seg[y].ff);
};
auto comp_go = [&](int x, int y) {
x = get_go(x); y = get_go(y);
if (x == y) return false;
if (isAnc(x, y)) return false;
if (isAnc(y, x)) return true;
return !(seg[y].ss < seg[x].ff);
};
priority_queue<int, vector<int>, decltype(comp_come)> come_pq(comp_come);
priority_queue<int, vector<int>, decltype(comp_go)> go_pq(comp_go);
auto relax_come = [&](int p) {
debug("relax_come", p);
if (seg[get_come(p)].ss < seg[get_come(come)].ff) return;
if (seg[get_come(p)].ss < seg[get_go(go)].ff) return;
if (seg[get_go(go)].ss <= seg[get_come(p)].ff) {
flag = true;
return;
}
if (comp_come(come, p)) come = p;
come_pq.push(p);
};
auto relax_go = [&](int p) {
debug("relax_go", p);
if (seg[get_go(go)].ss < seg[get_go(p)].ff) return;
if (seg[get_come(come)].ss < seg[get_go(p)].ff) return;
if (seg[get_go(p)].ss <= seg[get_come(come)].ff) {
flag = true;
return;
}
if (comp_go(go, p)) go = p;
go_pq.push(p);
};
relax_come(u);
relax_go(v);
vector<int> todo_come;
vector<int> todo_go;
debug("ok");
while (!flag) {
debug("gao", come, seg[pos[come]], go, seg[pos[go]]);
if (seg[get_come(come)].ss < seg[get_go(go)].ff) break;
if (seg[get_go(go)].ss <= seg[get_come(come)].ff)
return 1;
assert(isAnc(get_come(come), get_go(go)) ||
isAnc(get_go(go), get_come(come)));
if (isAnc(get_come(come), get_go(go))) {
debug("come");
assert(!come_pq.empty());
int now = come_pq.top();
come_pq.pop();
if (seg[get_come(now)].ss < seg[get_come(come)].ff) continue;
push_node(now, -1, seg[get_go(go)].ss);
todo_come.pb(now);
for (int i : rev[now])
relax_come(i);
}
else {
debug("go");
assert(!go_pq.empty());
int now = go_pq.top();
go_pq.pop();
if (seg[get_go(go)].ss < seg[get_go(now)].ff) continue;
push_node(now, seg[get_come(come)].ff, k);
todo_go.pb(now);
for (int i : g[now])
relax_go(i);
}
}
reverse(iter(todo_come));
reverse(iter(todo_go));
for (int now : todo_come) {
push_node(now, -1, seg[get_go(go)].ss);
for (int i : g[now])
push_node(i, seg[get_come(now)].ff, k);
}
for (int now : todo_go) {
push_node(now, seg[get_come(come)].ff, k);
for (int i : rev[now])
push_node(i, -1, seg[get_go(now)].ss);
}
if (flag) return 1;
if (seg[get_come(come)].ss < seg[get_go(go)].ff) return 0;
if (seg[get_go(go)].ss <= seg[get_come(come)].ff) return 1;
return 0;
}
