#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_ctr = 0;
bool k_can_reach[MAX_N], can_reach_k[MAX_N];
struct Node {
set<int> parents, children;
} k_reach_nodes[MAX_N], nodes_reach_k[MAX_N];
void init(int n, int k) {
n_ctr = n;
rep(i, k) k_can_reach[i] = true, can_reach_k[i] = true;
}
int add_teleporter(int u, int v) {
if (k_can_reach[u] && can_reach_k[v]) return 1;
if (u == v) return 0;
if (k_can_reach[u] && !k_can_reach[v]) {
vint st; st.push_back(v);
while (!st.empty()) {
int val = st.back(); st.pop_back();
k_can_reach[val] = true;
for (auto& p: k_reach_nodes[val].parents) k_reach_nodes[p].children.erase(val);
for (auto& c: k_reach_nodes[val].children) st.push_back(c);
}
}
if (can_reach_k[v] && !can_reach_k[u]) {
vint st; st.push_back(u);
while (!st.empty()) {
int val = st.back(); st.pop_back();
can_reach_k[val] = true;
for (auto& p: nodes_reach_k[val].parents) nodes_reach_k[p].children.erase(val);
for (auto& c: nodes_reach_k[val].children) st.push_back(c);
}
}
if (!k_can_reach[u] && !k_can_reach[v]) {
k_reach_nodes[u].children.insert(v);
k_reach_nodes[v].parents.insert(u);
}
if (!can_reach_k[v] && !can_reach_k[u]) {
nodes_reach_k[v].children.insert(u);
nodes_reach_k[u].parents.insert(v);
}
return 0;
}
