#include <bits/stdc++.h>
using namespace std;
struct fake_DSU {
vector<vector<int>> adj, rev;
vector<bool> to, from;
int s;
bool cyclic = false;
fake_DSU(int n, int s) : adj(n), rev(n), to(n), from(n), s(s) {
from[s] = to[s] = true;
}
void activate(int type, int u) {
auto &arr = type == 0 ? to : from;
if (arr[u]) return;
auto &nxt = type == 0 ? adj[u] : rev[u];
arr[u] = true;
for (int v : nxt) {
if (arr[v]) continue;
activate(type, v);
}
}
bool add_edge(int u, int v) {
if (cyclic) return cyclic;
cyclic |= to[u] && from[v];
adj[u].push_back(v);
rev[v].push_back(u);
if (to[u])
activate(0, v);
if (from[v])
activate(1, u);
return cyclic;
}
};
vector<fake_DSU> dsu;
int n;
void init(int _n, int k) {
n = _n;
for (int i = 0; i < k; i++)
dsu.emplace_back(n, i);
for (int u = 0; u < k-2; u++) {
for (int i = 0; i < k; i++)
dsu[i].add_edge(u, u+1);
}
}
int add_teleporter(int u, int v) {
for (int i = 0; i < dsu.size(); i++) {
if (dsu[i].add_edge(u, v)) return 1;
}
return 0;
}
