#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define left dsafh
#define right dslafh
#define N 300000
#define L 20
bool left[L][N], right[L][N], done;
int ind[L][N];
vector<int> g[N], gg[N];
int k;
void build(int top, int l, int r, int lvl) {
int m = l + r >> 1;
for (int i = l; i <= m; ++i) {
ind[lvl][i] = top;
left[lvl][i] = 1;
}
for (int i = m; i < r; ++i) {
ind[lvl][i] = top;
right[lvl][i] = 1;
}
if (l < m)
build(top * 2 + 1, l, m, lvl + 1);
if (m + 1 < r)
build(top * 2 + 2, m + 1, r, lvl + 1);
}
void init(int n, int k_) {
memset(ind, -1, sizeof ind);
k = k_;
build(0, 0, k, 0);
for (int i = 0; i < n; ++i)
ind[0][i] = 0;
}
vector<int> ladd, radd;
void addright(int v, int lvl) {
if (right[lvl][v])
return;
radd.push_back(v);
ind[lvl + 1][v] = ind[lvl][v] * 2 + 2;
right[lvl][v] = 1;
if (left[lvl][v])
done = 1;
for (int i = 0; i < (int)g[v].size(); ++i)
if (ind[lvl][g[v][i]] == ind[lvl][v])
addright(g[v][i], lvl);
}
void addleft(int v, int lvl) {
if (left[lvl][v])
return;
ladd.push_back(v);
ind[lvl + 1][v] = ind[lvl][v] * 2 + 1;
left[lvl][v] = 1;
if (right[lvl][v])
done = 1;
for (int i = 0; i < (int)gg[v].size(); ++i)
if (ind[lvl][gg[v][i]] == ind[lvl][v])
addleft(gg[v][i], lvl);
}
void run(int l, int r, int u, int v, bool edg, vector<int> &add, int lvl) {
if (!edg && add.empty())
return;
int m = l + r >> 1;
ladd.clear();
radd.clear();
for (int i = 0; i < (int)add.size(); ++i) {
int v = add[i];
for (int j = 0; j < (int)gg[v].size(); ++j)
if (right[lvl][gg[v][j]] && ind[lvl][gg[v][j]] == ind[lvl][v])
addright(v, lvl);
for (int j = 0; j < (int)g[v].size(); ++j)
if (left[lvl][g[v][j]] && ind[lvl][g[v][j]] == ind[lvl][v])
addleft(v, lvl);
}
if (edg) {
if (right[lvl][u])
addright(v, lvl);
if (left[lvl][v])
addleft(u, lvl);
}
vector<int> ladd1 = ladd, radd1 = radd;
if (m + 1 < r) {
run(m + 1, r, u, v,
u != m && v != m && edg && right[lvl][u] && right[lvl][v], radd1,
lvl + 1);
}
if (l < m) {
run(l, m, u, v, edg && u != m && v != m && left[lvl][u] && left[lvl][v],
ladd1, lvl + 1);
}
}
int add_teleporter(int u, int v) {
if (u == v && u < k)
return 1;
g[u].push_back(v);
gg[v].push_back(u);
vector<int> vec;
run(0, k, u, v, 1, vec, 0);
return done;
}
