#include <bits/stdc++.h>
using namespace std;
const int N = 310000;
int l[N], r[N], kk;
vector<int> out[N], in[N];
void init(int n, int k) {
kk = k;
for (int i = 0; i <= k; i++)
l[i] = r[i] = i;
for (int i = k + 1; i <= n; i++)
l[i] = 0, r[i] = k;
}
bool upd_edge(int u, int v);
bool upd_vert(int v) {
for (int u : in[v]) if (upd_edge(u, v)) return true;
for (int u : out[v]) if (upd_edge(v, u)) return true;
return false;
}
bool upd_edge(int u, int v) {
if (r[u] < l[v]) return false;
if (r[v] < l[u]) return true;
int mu = (l[u] + r[u]) / 2;
int mv = (l[v] + r[v]) / 2;
if (r[v] < r[u] && r[v] <= mu) {
r[u] = mu;
return upd_vert(u);
}
if (l[u] > mv) {
l[v] = mv + 1;
return upd_vert(v);
}
return false;
}
int add_teleporter(int u, int v) {
u++; v++;
if (v <= kk) v--;
in[v].push_back(u);
out[u].push_back(v);
return upd_edge(u, v);
}
