#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int N = 3e4+4, K = 1e3+3, X = 1e3+3;
mt19937 rng(time(nullptr));
bool cycle;
int n, k, nodes[X];
vector<int> adj[N], adj2[N];
bitset<N> st, nd, sp;
bitset<K> bt[X];
void dfs2(int u) {
st[u] = 1;
for (int& v : adj2[u]) {
if (st[v]) continue;
dfs2(v);
}
}
void dfs(int u) {
nd[u] = 1;
for (int& v : adj[u]) {
if (nd[v]) continue;
dfs(v);
}
}
void init(int N, int K) {
n = N;
k = K;
cycle = 0;
for (int i = 0; i < n; i++) {
adj[i].clear();
adj2[i].clear();
}
for (int i = 0; i+1 < k; i++) {
adj[i].push_back(i+1);
adj2[i+1].push_back(i);
}
sp.reset();
for (int i = 0; i < X; i++) {
bt[i].reset();
nodes[i] = rng() % n;
sp[nodes[i]] = 1;
}
}
int add_teleporter(int u, int v) {
if (cycle) return 1;
adj[u].push_back(v);
adj2[v].push_back(u);
st.reset();
nd.reset();
dfs(v);
dfs2(u);
bool b = 0;
for (int i = 0; i < k; i++) {
if (st[i] && st[i] == nd[i]) b = 1;
}
return cycle = b;
}
