#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct Solver {
static constexpr unsigned char AL = 1, FF = 2, BB = 4;
struct Node {
int l, r, mid, left, right;
};
struct Event {
unsigned char type; // 0=allow, 1=add F, 2=add B, 3=use edge
int node, u, v;
};
int n = 0, k = 0, root = -1;
vector<Node> seg;
vector<vector<int>> g, rg;
bool bad = false;
vector<unsigned long long> hkey;
vector<unsigned char> hval;
size_t hmask = 0;
vector<Event> st;
static unsigned long long splitmix64(unsigned long long x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
unsigned long long makeKey(int node, int v) const {
return ((unsigned long long)(unsigned)node << 32) | (unsigned)(v + 1);
}
void initHash(size_t expected) {
size_t cap = 1;
while (cap < expected * 2 + 100) cap <<= 1;
hkey.assign(cap, 0);
hval.assign(cap, 0);
hmask = cap - 1;
}
unsigned char getFlags(int node, int v) const {
unsigned long long key = makeKey(node, v);
size_t pos = splitmix64(key) & hmask;
while (hkey[pos]) {
if (hkey[pos] == key) return hval[pos];
pos = (pos + 1) & hmask;
}
return 0;
}
unsigned char& refFlags(int node, int v) {
unsigned long long key = makeKey(node, v);
size_t pos = splitmix64(key) & hmask;
while (hkey[pos] && hkey[pos] != key) {
pos = (pos + 1) & hmask;
}
if (!hkey[pos]) {
hkey[pos] = key;
hval[pos] = 0;
}
return hval[pos];
}
bool setFlag(int node, int v, unsigned char bit) {
unsigned char& f = refFlags(node, v);
if (f & bit) return false;
f |= bit;
return true;
}
int build(int l, int r) {
if (l > r) return -1;
int id = (int)seg.size();
int m = (l + r) / 2;
seg.push_back({l, r, m, -1, -1});
seg[id].left = build(l, m - 1);
seg[id].right = build(m + 1, r);
return id;
}
bool isAllowed(int node, int v) const {
if (node == -1) return false;
if (node == root) return true;
return getFlags(node, v) & AL;
}
bool inF(int node, int v) const {
return getFlags(node, v) & FF;
}
bool inB(int node, int v) const {
return getFlags(node, v) & BB;
}
void pushAllow(int node, int x) {
if (!bad && node != -1) st.push_back({0, node, x, 0});
}
void pushF(int node, int x) {
if (!bad && node != -1) st.push_back({1, node, x, 0});
}
void pushB(int node, int x) {
if (!bad && node != -1) st.push_back({2, node, x, 0});
}
void pushEdge(int node, int u, int v) {
if (!bad && node != -1) st.push_back({3, node, u, v});
}
void handleAllow(int node, int x) {
if (bad || node == -1) return;
if (node == root) return;
if (!setFlag(node, x, AL)) return;
if (x == seg[node].mid) {
pushF(node, x);
pushB(node, x);
}
for (int y : rg[x]) pushEdge(node, y, x);
for (int y : g[x]) pushEdge(node, x, y);
}
void handleF(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
if (!setFlag(node, x, FF)) return;
// Right child gets vertices reachable from this midpoint.
if (seg[node].right != -1 && x != seg[node].mid) {
pushAllow(seg[node].right, x);
}
for (int y : g[x]) {
pushEdge(node, x, y);
}
}
void handleB(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
if (!setFlag(node, x, BB)) return;
// Left child gets vertices that can reach this midpoint.
if (seg[node].left != -1 && x != seg[node].mid) {
pushAllow(seg[node].left, x);
}
for (int y : rg[x]) {
pushEdge(node, y, x);
}
}
void handleEdge(int node, int u, int v) {
if (bad || node == -1) return;
if (!isAllowed(node, u) || !isAllowed(node, v)) return;
// mid -> ... -> u -> v -> ... -> mid
if (inF(node, u) && inB(node, v)) {
bad = true;
return;
}
// If mid can reach u, then mid can reach v.
if (inF(node, u)) {
pushF(node, v);
}
// If v can reach mid, then u can reach mid.
if (inB(node, v)) {
pushB(node, u);
}
}
void runEvents() {
while (!st.empty() && !bad) {
Event e = st.back();
st.pop_back();
if (e.type == 0) handleAllow(e.node, e.u);
else if (e.type == 1) handleF(e.node, e.u);
else if (e.type == 2) handleB(e.node, e.u);
else handleEdge(e.node, e.u, e.v);
}
if (bad) st.clear();
}
void processNewEdge(int node, int u, int v) {
if (bad || node == -1) return;
if (!isAllowed(node, u) || !isAllowed(node, v)) return;
pushEdge(node, u, v);
runEvents();
if (bad) return;
processNewEdge(seg[node].left, u, v);
if (bad) return;
processNewEdge(seg[node].right, u, v);
}
void initSolver(int N, int K) {
n = N;
k = K;
root = -1;
bad = false;
seg.clear();
st.clear();
g.assign(n, {});
rg.assign(n, {});
for (int i = 0; i + 1 < k; i++) {
g[i].push_back(i + 1);
rg[i + 1].push_back(i);
}
if (k == 0) {
initHash(1);
return;
}
root = build(0, k - 1);
int depth = 0;
for (int t = max(1, k); t; t >>= 1) depth++;
initHash((size_t)n * (depth + 2) + 10);
pushF(root, seg[root].mid);
pushB(root, seg[root].mid);
runEvents();
}
int addEdge(int u, int v) {
if (bad) return 1;
g[u].push_back(v);
rg[v].push_back(u);
processNewEdge(root, u, v);
return bad ? 1 : 0;
}
};
static Solver solver;
void init(int n, int k) {
solver.initSolver(n, k);
}
int add_teleporter(int u, int v) {
return solver.addEdge(u, v);
}
