#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 = 0, k = 0, root = -1;
vector<Node> seg;
vector<vector<int>> g, rg;
// For every segment-tree node:
// allowed[node] = vertices allowed in this subproblem
// F[node] = vertices reachable from mid
// B[node] = vertices that can reach mid
vector<set<int>> allowed, F, B;
bool bad = false;
int build(int l, int r);
bool isAllowed(int node, int v) const;
bool inF(int node, int v) const;
bool inB(int node, int v) const;
void dfsForward(int node, int x);
void dfsBackward(int node, int x);
void allowVertex(int node, int x);
void useEdge(int node, int u, int v);
void processNewEdge(int node, int u, int v);
void initSolver(int N, int K);
int addEdge(int u, int v);
};
int Solver::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 Solver::isAllowed(int node, int v) const {
if (node == -1) return false;
if (node == root) return true;
return allowed[node].find(v) != allowed[node].end();
}
bool Solver::inF(int node, int v) const {
return F[node].find(v) != F[node].end();
}
bool Solver::inB(int node, int v) const {
return B[node].find(v) != B[node].end();
}
void Solver::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 (inF(node, u) && inB(node, v)) {
bad = true;
return;
}
// If mid can reach u, then now mid can reach v.
if (inF(node, u)) {
dfsForward(node, v);
if (bad) return;
}
// If v can reach mid, then now u can reach mid.
if (inB(node, v)) {
dfsBackward(node, u);
if (bad) return;
}
}
void Solver::dfsForward(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
if (inF(node, x)) return;
F[node].insert(x);
// Right subproblem only needs vertices reachable from this midpoint.
// We exclude the midpoint itself; cycles using it are detected here.
if (seg[node].right != -1 && x != seg[node].mid) {
allowVertex(seg[node].right, x);
if (bad) return;
}
for (int y : g[x]) {
useEdge(node, x, y);
if (bad) return;
}
}
void Solver::dfsBackward(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
if (inB(node, x)) return;
B[node].insert(x);
// Left subproblem only needs vertices that can reach this midpoint.
// We exclude the midpoint itself; cycles using it are detected here.
if (seg[node].left != -1 && x != seg[node].mid) {
allowVertex(seg[node].left, x);
if (bad) return;
}
for (int y : rg[x]) {
useEdge(node, y, x);
if (bad) return;
}
}
void Solver::allowVertex(int node, int x) {
if (bad || node == -1) return;
bool inserted = allowed[node].insert(x).second;
if (!inserted) return;
// If this subproblem's midpoint becomes allowed, start DFS from it.
if (x == seg[node].mid) {
dfsForward(node, x);
if (bad) return;
dfsBackward(node, x);
if (bad) return;
}
// Existing edges touching x may now become usable inside this subproblem.
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 Solver::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);
}
void Solver::initSolver(int N, int K) {
n = N;
k = K;
root = -1;
bad = false;
seg.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) return;
root = build(0, k - 1);
int nodes = (int)seg.size();
allowed.assign(nodes, {});
F.assign(nodes, {});
B.assign(nodes, {});
dfsForward(root, seg[root].mid);
if (!bad) dfsBackward(root, seg[root].mid);
}
int Solver::addEdge(int u, int v) {
if (bad) return 1;
g[u].push_back(v);
rg[v].push_back(u);
if (root != -1) {
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);
}
