#include <bits/stdc++.h>
using namespace std;
vector<int> adj[300000], rev[300000];
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;
}
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;
}
// void O(int x) { cout << x << "\n"; }
// int main() {
// init(6, 3);
// O(add_teleporter(3, 4));
// O(add_teleporter(5, 0));
// O(add_teleporter(4, 5));
// O(add_teleporter(5, 3));
// O(add_teleporter(1, 4));
// }
