//Challenge: Accepted
//#define _GLIBCXX_DEBUG 1
#include "game.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1e9;
int in[maxn], out[maxn];
int block[maxn];
vector<int> adj[maxn], rev[maxn];
int N, K;
void init(int n, int k) {
N = n, K = k;
for (int i = 0;i < n;i++) {
in[i] = inf, out[i] = -inf;
block[i] = 19;
}
for (int i = 0;i < k - 1;i++) {
adj[i].push_back(i + 1);
}
for (int i = 0;i < k;i++) {
in[i] = i, out[i] = i;
block[i] = 0;
}
}
bool dfs(int n, int d, int type, vector<int> &add) {
bool ret = 0;
if (n >= K && in[n] <= out[n]) return 1;
if (in[n] / (1<<d) == out[n] / (1<<d) && block[n] > d) {
block[n] = d;
add.push_back(n);
}
if (type == 0) {
for (int i:adj[n]) {
if (block[i] <= d+1 && out[i] / (1<<d) < out[n] / (1<<d)) {
out[i] = out[n];
ret |= dfs(i, d, type, add);
}
}
} else {
for (int i:rev[n]) {
if (block[i] <= d+1 && in[i] / (1<<d) > in[n] / (1<<d)) {
in[i] = in[n];
ret |= dfs(i, d, type, add);
}
}
}
return ret;
}
bool solve(int u, int v, int d, vector<int> check) {
if (d < 0) return 0;
if (block[v] <= d && out[v] / (1<<(d-1)) < out[u] / (1<<(d-1))) {
check.push_back(v);
}
if (block[u] <= d && in[u] / (1<<(d-1)) > in[v] / (1<<(d-1))) {
check.push_back(u);
}
vector<int> rec;
for (int i:check) {
for (int j:adj[i]) in[i] = min(in[i], in[j]);
for (int j:rev[i]) out[i] = max(out[i], out[j]);
if (dfs(i, d-1, 0, rec) || dfs(i, d-1, 1, rec)) return 1;
}
return solve(u, v, d-1, rec);
}
int add_teleporter(int u, int v) {
if (u < K && v < K) {
if (u >= v) return 1;
}
adj[u].push_back(v);
rev[v].push_back(u);
vector<int> tmp;
int val = solve(u, v, 19, tmp);
return val;
}
