#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;
};
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;
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 + 10) 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 useEdge(int node, int u, int v) {
if (bad || node == -1) return;
if (!isAllowed(node, u) || !isAllowed(node, v)) return;
if (inF(node, u) && inB(node, v)) {
bad = true;
return;
}
if (inF(node, u)) {
dfsForward(node, v);
if (bad) return;
}
if (inB(node, v)) {
dfsBackward(node, u);
if (bad) return;
}
}
void dfsForward(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
if (!setFlag(node, x, FF)) return;
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 dfsBackward(int node, int x) {
if (bad || node == -1 || !isAllowed(node, x)) return;
if (!setFlag(node, x, BB)) return;
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 allowVertex(int node, int x) {
if (bad || node == -1) return;
if (!setFlag(node, x, AL)) return;
if (x == seg[node].mid) {
dfsForward(node, x);
if (bad) return;
dfsBackward(node, x);
if (bad) return;
}
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 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 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) {
initHash(1);
return;
}
root = build(0, k - 1);
int depth = 0;
int t = max(1, k);
while (t > 0) {
depth++;
t >>= 1;
}
initHash((size_t)n * (depth + 3));
dfsForward(root, seg[root].mid);
if (!bad) dfsBackward(root, seg[root].mid);
}
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);
}
