#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e4 + 5;
int n, k, K;
set<int> in_l[MAX], in_r[MAX];
vector<int> Gf[MAX], Gr[MAX];
void init(int n_, int k_) {
n = n_, k = k_;
K = k <= 1 ? 1 : 1 << (32 - __builtin_clz(k - 1));
}
bool add(int, int, bool);
bool insert_f(int v, int i) {
if (!in_r[v].contains(i))
return add(v, i, true);
return false;
}
bool insert_r(int v, int i) {
if (!in_l[v].contains(i))
return add(v, i, false);
return false;
}
bool add(int v, int c, bool side) {
if ((side ? in_l : in_r)[v].contains(c ^ c < 2 * K))
return true;
(side ? in_r : in_l)[v].insert(c);
if (side) {
for (int u : Gf[v]) {
if (insert_f(u, c))
return true;
}
}
else {
for (int u : Gr[v]) {
if (insert_r(u, c))
return true;
}
}
return false;
}
int add_teleporter(int u, int v) {
if (u < k && v < k) {
if (u >= v)
return true;
return false;
}
if (u < k) {
if (insert_f(v, 2 * K + u))
return true;
for (int i = K + u; i > 0; i >>= 1)
if (i & 1 && insert_f(v, i))
return true;
}
if (v < k) {
if (insert_r(u, 2 * K + v))
return true;
for (int i = K + v; i > 0; i >>= 1)
if (!(i & 1) && insert_r(u, i))
return true;
}
if (u >= k && v >= k) {
Gf[u].push_back(v);
Gr[v].push_back(u);
for (int i : in_r[u])
if (insert_f(v, i))
return true;
for (int i : in_l[v])
if (insert_r(u, i))
return true;
}
return false;
}
