#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct Solver {
struct Node {
int l, r, mid;
int left = -1, right = -1;
};
int n, k, root = -1;
vector<Node> seg;
vector<vector<int>> g, rg;
// These store pairs (segment_tree_node, vertex).
unordered_set<unsigned long long> allowed;
unordered_set<unsigned long long> F; // reachable from mid
unordered_set<unsigned long long> B; // can reach mid
bool bad = false;
unsigned long long key(int node, int v) const {
return (unsigned long long)(unsigned)node << 32 | (unsigned)v;
}
bool has(const unordered_set<unsigned long long>& s, int node, int v) const {
return s.find(key(node, v)) != s.end();
}
bool isAllowed(int node, int v) const {
return node == root || has(allowed, node, v);
}
int build(int l, int r) {
if (l > r) return -1;
int id = (int)seg.size();
int mid = (l + r) / 2;
seg.push_back({l, r, mid, -1, -1});
seg[id].left = build(l, mid - 1);
seg[id].right = build(mid + 1, r);
return id;
}
void useEdge(int node, int u, int v);
void dfsForward(int node, int x);
void dfsBackward(int node, int x);
void allowVertex(int node, int x);
void dfsForward(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
auto K = key(node, x);
if (F.find(K) != F.end()) return;
F.insert(K);
// Right child only needs vertices reachable from this midpoint.
if (seg[node].right != -1) {
allowVertex(seg[node].right, x);
if (bad) return;
}
// Normal DFS direction.
for (int y : g[x]) {
useEdge(node, x, y);
if (bad) return;
}
}
void dfsBackward(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
auto K = key(node, x);
if (B.find(K) != B.end()) return;
B.insert(K);
// Left child only needs vertices that can reach this midpoint.
if (seg[node].left != -1) {
allowVertex(seg[node].left, x);
if (bad) return;
}
// Reverse DFS direction.
for (int y : rg[x]) {
useEdge(node, y, x);
if (bad) return;
}
}
void allowVertex(int node, int x) {
if (bad || node == -1) return;
if (node == root) return;
auto K = key(node, x);
if (allowed.find(K) != allowed.end()) return;
allowed.insert(K);
// If the middle special vertex itself became allowed,
// start the two DFS searches for this subproblem.
if (x == seg[node].mid) {
dfsForward(node, x);
if (bad) return;
dfsBackward(node, x);
if (bad) return;
}
// x just became allowed, so old edges touching x may now matter.
for (int y : rg[x]) {
useEdge(node, y, x);
if (bad) return;
}
for (int y : g[x]) {
useEdge(node, x, y);
if (bad) return;
}
}
void useEdge(int node, int u, int v) {
if (bad || node == -1) return;
if (!isAllowed(node, u) || !isAllowed(node, v)) return;
// mid -> ... -> u -> v -> ... -> mid
if (has(F, node, u) && has(B, node, v)) {
bad = true;
return;
}
// If mid can reach u, then now mid can reach v.
if (has(F, node, u)) {
dfsForward(node, v);
if (bad) return;
}
// If v can reach mid, then now u can reach mid.
if (has(B, node, v)) {
dfsBackward(node, u);
if (bad) return;
}
}
void processNewEdge(int node, int u, int v) {
if (bad || node == -1) return;
if (!isAllowed(node, u) || !isAllowed(node, v)) return;
useEdge(node, u, v);
if (bad) return;
processNewEdge(seg[node].left, u, v);
if (bad) return;
processNewEdge(seg[node].right, u, v);
if (bad) return;
}
void initSolver(int N, int K) {
n = N;
k = K;
g.assign(n, {});
rg.assign(n, {});
// Initial edges: 0 -> 1 -> ... -> k - 1
for (int i = 0; i + 1 < k; i++) {
g[i].push_back(i + 1);
rg[i + 1].push_back(i);
}
if (k == 0) return;
root = build(0, k - 1);
allowed.reserve((size_t)n * 20);
F.reserve((size_t)n * 20);
B.reserve((size_t)n * 20);
// Root allows every vertex.
// Start DFS from its middle special vertex.
int m = seg[root].mid;
dfsForward(root, m);
dfsBackward(root, m);
}
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);
}
