#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> mn, mx;
vector<vector<int>> gr, grr;
int kk;
void init(int n, int k) {
kk = k;
mn.resize(n, k + 1);
mx.assign(n, 0);
gr.resize(n);
grr.resize(n);
for (int i = 0; i < k; i++) {
mn[i] = i + 1;
mx[i] = i + 1;
}
}
bool check_vert(int v);
bool check_edge(int u, int v) {
if (mn[v] <= mx[u]) return 1;
if (((mn[u] + mx[u]) / 2) >= mn[v]) {
mn[u] = ((mn[u] + mx[u]) / 2);
if (check_vert(u)) return 1;
}
if (((mn[v] + mx[v]) / 2) <= mx[u]) {
mx[v] = ((mn[v] + mx[v]) / 2);
if (check_vert(v)) return 1;
}
return 0;
}
bool check_vert(int v) {
if (v < kk) return 0;
if (mn[v] <= mx[v]) return 1;
for (auto &i : gr[v]) {
if (check_edge(v, i)) return 1;
}
for (auto &i : grr[v]) {
if (check_edge(i, v)) return 1;
}
return 0;
}
int add_teleporter(int u, int v) {
gr[u].push_back(v);
grr[v].push_back(u);
return check_edge(u, v);
}
