#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int N = 3e5, n2, K, tin;
vector<vector<int>> to(N), rt(N);
vector<bool> vis(N);
vector<int> post_order, gp(N);
void dfs(int u){
vis[u] = 1;
for (int v: to[u]){
if (!vis[v]) dfs(v);
}
post_order.push_back(u);
}
void rdfs(int u){
vis[u] = 1;
gp[u] = tin;
for (int v: rt[u]){
if (!vis[v]) rdfs(v);
}
}
void init(int n, int k){
K = k;
n2 = n;
for (int i = 0; i < k - 1; i++){
to[i].push_back(i + 1);
rt[i + 1].push_back(i);
}
}
int add_teleporter(int u, int v){
int n = n2;
post_order.clear();
for (int i = 0; i < n; i++){
vis[i] = 0;
gp[i] = -1;
}
if (u == v){
if (u < K) return 1;
return 0;
}
to[u].push_back(v);
rt[v].push_back(u);
for (int i = 0; i < n; i++){
if (!vis[i]) dfs(i);
}
reverse(post_order.begin(), post_order.end());
for (int i = 0; i < n; i++) vis[i] = 0;
tin = 0;
for (int u: post_order){
if (!vis[u]){
rdfs(u);
tin++;
}
}
vector<bool> b1(tin), b2(tin);
for (int i = 0; i < n; i++){
if (i < K) b1[gp[i]] = 1;
else b2[gp[i]] = 1;
}
for (int i = 0; i < tin; i++){
if (b1[i] && b2[i]) return 1;
}
return 0;
}
