#include <bits/stdc++.h>
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using pill = pair<int, ll>;
using vpill = vector<pill>;
using plli = pair<ll, int>;
using vplli = vector<plli>;
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n)-1; i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a)-1; i >= (b); --i)
const int MAX_N = 3e5;
int n, k;
struct Node {
set<int> parents, children;
int k_fw, k_bw;
} nodes[MAX_N];
void init(int _n, int _k) {
n = _n, k = _k;
FOR(i, 0, k) nodes[i].k_fw = i, nodes[i].k_bw = i;
FOR(i, k, n) nodes[i].k_fw = k, nodes[i].k_bw = -1;
}
int add_teleporter(int u, int v) {
if (u < k && v < k) {
if (v <= u) return 1;
return 0;
}
if (u == v) return 0;
nodes[u].children.insert(v);
nodes[v].parents.insert(u);
if (nodes[v].k_bw < nodes[u].k_bw) {
int n_bw = nodes[u].k_bw;
nodes[v].k_bw = n_bw;
bool found = false;
auto dfs_fw = [&](auto& self, int val) -> void {
nodes[val].k_bw = n_bw;
if (nodes[val].k_fw <= nodes[val].k_bw && val >= k) found = true;
for (auto& c: nodes[val].children)
if (nodes[c].k_bw < n_bw) self(self, c);
};
dfs_fw(dfs_fw, v);
if (found) return 1;
}
if (nodes[u].k_fw > nodes[v].k_fw) {
int n_fw = nodes[v].k_fw;
nodes[u].k_fw = n_fw;
bool found = false;
auto dfs_bw = [&](auto& self, int val) -> void {
nodes[val].k_fw = n_fw;
if (nodes[val].k_fw <= nodes[val].k_bw && val >= k) found = true;
for (auto& p: nodes[val].parents)
if (nodes[val].k_fw > n_fw) self(self, p);
};
dfs_bw(dfs_bw, u);
if (found) return 1;
}
return 0;
}
