#include <bits/stdc++.h>
using namespace std;
static vector<vector<int>> adj, rev;
struct fake_DSU {
vector<char> to, from;
fake_DSU() {}
fake_DSU(int n, int s) : to(n, 0), from(n, 0) {
to[s] = from[s] = 1;
}
void activate(int type, int st) {
auto &arr = (type == 0 ? to : from);
if (arr[st]) return;
stack<int> stk;
stk.push(st);
arr[st] = 1;
while (!stk.empty()) {
int u = stk.top();
stk.pop();
auto &nxt = (type == 0 ? adj[u] : rev[u]);
for (int v : nxt) {
if (arr[v]) continue;
arr[v] = 1;
stk.push(v);
}
}
}
bool would_cycle(int u, int v) const {
return to[u] && from[v];
}
void apply_edge(int u, int v) {
if (to[u]) activate(0, v);
if (from[v]) activate(1, u);
}
};
vector<fake_DSU> dsu;
void init(int n, int k) {
adj.assign(n, {});
rev.assign(n, {});
dsu.clear();
dsu.reserve(k);
for (int i = 0; i < k; i++) dsu.emplace_back(n, i);
for (int u = 0; u < k - 1; u++) {
adj[u].push_back(u + 1);
rev[u + 1].push_back(u);
}
for (int i = 0; i < k; i++) {
for (int u = 0; u < k - 1; u++) {
dsu[i].apply_edge(u, u + 1);
}
}
}
int add_teleporter(int u, int v) {
for (int i = 0; i < (int)dsu.size(); i++) {
if (dsu[i].would_cycle(u, v)) return 1;
}
adj[u].push_back(v);
rev[v].push_back(u);
for (int i = 0; i < (int)dsu.size(); i++) {
dsu[i].apply_edge(u, v);
}
return 0;
}
