#include "game.h"
#include <algorithm>
#include <utility>
#include <vector>
namespace kod {
using namespace std;
int n, k;
vector<int> l, r;
vector<vector<int>> in, out;
int get_level(const int u) { return l[u] >= r[u] ? 0 : 32 - __builtin_clz(l[u] ^ r[u]); }
bool check_vertex(const int u);
bool check_edge(const int u, const int v);
bool check_vertex(const int x) {
for (const int y : out[x]) {
if (check_edge(x, y)) {
return true;
}
}
for (const int y : in[x]) {
if (check_edge(y, x)) {
return true;
}
}
return false;
}
bool check_edge(const int u, const int v) {
const int u0 = get_level(u);
const int v0 = get_level(v);
r[u] = min(r[u], v <= k ? v : r[v]);
l[v] = max(l[v], u <= k ? u : l[u]);
const int u1 = get_level(u);
const int v1 = get_level(v);
if (u1 == 0 or v1 == 0) {
return true;
}
if (u1 < u0 and check_vertex(u)) {
return true;
}
if (v1 < v0 and check_vertex(v)) {
return true;
}
return false;
}
int add_edge(const int u, const int v) {
in[v].push_back(u);
out[u].push_back(v);
return check_edge(u, v);
}
void init(const int n_, const int k_) {
n = n_;
k = k_;
l.resize(n + 1, 0);
r.resize(n + 1, n + 1);
in.resize(n + 1);
out.resize(n + 1);
for (int i = 1; i <= k - 1; ++i) {
add_edge(i, i + 1);
}
}
} // namespace kod
void init(int n, int k) { kod::init(n, k); }
int add_teleporter(int u, int v) { return kod::add_edge(u + 1, v + 1); }
