#include <bits/stdc++.h>
using namespace std;
struct fake_DSU {
vector<vector<int>> adj, rev;
vector<char> to, from;
bool cyclic = false;
fake_DSU(int n, int s) : adj(n), rev(n), 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 add_edge(int u, int v) {
if (cyclic) return true;
if (to[u] && from[v]) {
cyclic = true;
return true;
}
adj[u].push_back(v);
rev[v].push_back(u);
if (to[u]) activate(0, v);
if (from[v]) activate(1, u);
return false;
}
};
vector<fake_DSU> dsu;
void init(int n, int k) {
dsu.reserve(k);
for (int i = 0; i < k; i++) dsu.emplace_back(n, i);
for (int u = 0; u < k - 1; 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 < (int)dsu.size(); i++) {
if (dsu[i].add_edge(u, v)) return 1;
}
return 0;
}
