#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 3e5+5;
int n, k;
int l[mxn];
int r[mxn];
vector<int> g[mxn];
vector<int> rg[mxn];
bool in_q[mxn];
void init(int N, int K) {
n = N;
k = K;
// CRITICAL FIX: Clear all global state for multiple test cases!
for(int i = 0; i < n; i++) {
l[i] = -1;
r[i] = k;
in_q[i] = false;
g[i].clear(); // Purge ghost edges
rg[i].clear(); // Purge ghost edges
}
for(int i = 0; i < k; i++){
l[i] = i;
r[i] = i;
}
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) {
// 1. Cycle purely contained within special nodes
if(v <= u && max(u, v) < k) return 1;
if(max(u, v) < k) return 0; // Forward shortcut among special nodes
// 2. IMMEDIATE CYCLE CHECK (Bulletproofing)
// If u can ALREADY be reached by a special node >= the special node v can reach
int max_in_u = (u >= k) ? l[u] - 1 : u;
int min_out_v = (v >= k) ? r[v] + 1 : v;
if (max_in_u >= min_out_v) return 1;
// Add edges
g[u].push_back(v);
rg[v].push_back(u);
queue<int> q;
// 3. Initial Queue Pushes
if (v >= k && (l[v] + r[v]) / 2 <= max_in_u && !in_q[v]) {
q.push(v);
in_q[v] = true;
}
if (u >= k && (l[u] + r[u]) / 2 >= min_out_v && !in_q[u]) {
q.push(u);
in_q[u] = true;
}
// 4. Process Amortized Queue
while(!q.empty()){
int node = q.front();
q.pop();
in_q[node] = false;
// Step A: Settle bounds continuously
bool changed = true;
while(changed) {
changed = false;
// Check incoming edges
for(int p : rg[node]){
int max_in_p = (p >= k) ? l[p] - 1 : p;
if(max_in_p >= (l[node] + r[node]) / 2) {
l[node] = (l[node] + r[node]) / 2 + 1;
if(l[node] > r[node]) return 1;
changed = true;
break; // Midpoint shifted, restart check
}
}
if(changed) continue;
// Check outgoing edges
for(int nx : g[node]){
int min_out_nx = (nx >= k) ? r[nx] + 1 : nx;
if(min_out_nx <= (l[node] + r[node]) / 2) {
r[node] = (l[node] + r[node]) / 2 - 1;
if(l[node] > r[node]) return 1;
changed = true;
break; // Midpoint shifted, restart check
}
}
}
// Step B: Wake up neighbors
for(int nx : g[node]){
if(nx >= k && (l[nx] + r[nx]) / 2 <= l[node] - 1 && !in_q[nx]){
q.push(nx);
in_q[nx] = true;
}
}
for(int p : rg[node]){
if(p >= k && (l[p] + r[p]) / 2 >= r[node] + 1 && !in_q[p]){
q.push(p);
in_q[p] = true;
}
}
}
return 0;
}
