#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)3e5 + 10;
vector<int> T[N];
vector<int> R[N];
pii G[N];
pii layer[N];
void init(int n, int k) {
for(int i = 1 ; i <= n; i ++ ){
if(i <= k){
G[i] = mp(i, i);
}
else{
G[i] = mp(0, k + 1);
}
layer[i] = mp(0, k + 1);
}
}
int explore(int u, int v){
if(G[u].fi >= G[v].se){
return 1;
}
if(G[u].fi > G[v].fi){
G[v].fi = G[u].fi;
}
if(G[v].se < G[u].se){
G[u].se = G[v].se;
}
if((layer[u].fi < layer[u].se) && (layer[u].fi + layer[u].se) / 2 >= G[u].se){
layer[u].se = (layer[u].fi + layer[u].se) / 2;
for(auto x : T[u]){
if(explore(u, x)) return 1;
}
for(auto x : R[u]){
if(explore(x, u)) return 1;
}
}
else if((layer[u].fi < layer[u].se) && (layer[u].fi + layer[u].se) / 2 < G[u].fi){
layer[u].fi = (layer[u].fi + layer[u].se) / 2 + 1;
for(auto x : T[u]){
if(explore(u, x)) return 1;
}
for(auto x : R[u]){
if(explore(x, u)) return 1;
}
}
else if((layer[v].fi < layer[v].se) && (layer[v].fi + layer[v].se) / 2 >= G[v].se){
layer[v].se = (layer[v].fi + layer[v].se) / 2;
for(auto x : T[v]){
if(explore(v, x)) return 1;
}
for(auto x : R[v]){
if(explore(x, v)) return 1;
}
}
else if((layer[v].fi < layer[v].se) && (layer[v].fi + layer[v].se) / 2 < G[v].fi){
layer[v].fi = (layer[v].fi + layer[v].se) / 2 + 1;
for(auto x : T[v]){
if(explore(v, x)) return 1;
}
for(auto x : R[v]){
if(explore(x, v)) return 1;
}
}
return 0;
}
int add_teleporter(int u, int v) {
u ++ ;
v ++ ;
T[u].push_back(v);
R[v].push_back(u);
return explore(u, v);
}
