#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int N = 300300;
int n, k;
vector<int> g[N];
vector<int> rg[N];
int cmp[N];
int tin[N], tout[N], T = 0;
bool vis[N];
void precalc(int s) {
vis[s] = true;
tin[s] = T++;
for (int to : g[s]) if (!vis[to]) {
precalc(to);
}
tout[s] = T++;
}
void dfs(int s, int c) {
vis[s] = true;
cmp[s] = c;
for (int to : rg[s]) if (!vis[to]) {
dfs(to, c);
}
}
void init(int N, int K) {
n = N, k = K;
for (int i = 0; i < k - 1; i++) {
g[i].push_back(i + 1);
rg[i + 1].push_back(i);
}
}
int add_teleporter(int u, int v) {
if (u == v && u < k) return 1;
T = 0;
for (int i = 0; i < n; i++) {
cmp[i] = 0;
tin[i] = tout[i] = 0;
vis[i] = false;
}
g[u].push_back(v);
rg[v].push_back(u);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
precalc(i);
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [](int x, int y) {
return tout[x] > tout[y];
});
for (int i = 0; i < n; i++) vis[i] = false;
int cnt = 1;
for (int c : ord) {
if (vis[c]) continue;
dfs(c, cnt++);
}
int sz[cnt] = {};
for (int i = 0; i < n; i++) {
sz[cmp[i]]++;
}
for (int i = 0; i < k; i++) {
if (sz[cmp[i]] > 1) {
return 1;
}
}
return 0;
}
