#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]; // CRITICAL: Prevents queue flooding and TLE
void init(int N, int K) {
n = N;
k = K;
fill(l, l + n, -1);
fill(r, r + n, k);
fill(in_q, in_q + n, false);
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. Immediate cycle check for special nodes
if(v <= u && max(u, v) < k) return 1;
if(max(u, v) < k) return 0;
g[u].push_back(v);
rg[v].push_back(u);
queue<int> q;
// 2. Initial pushes (Only push, don't use while loops here)
if (v >= k && (l[v] + r[v]) / 2 <= (u >= k ? l[u] - 1 : u) && !in_q[v]) {
q.push(v);
in_q[v] = true;
}
if (u >= k && (l[u] + r[u]) / 2 >= (v >= k ? r[v] + 1 : v) && !in_q[u]) {
q.push(u);
in_q[u] = true;
}
// 3. Process the queue
while(!q.empty()){
int node = q.front();
q.pop();
in_q[node] = false; // Mark as popped
// STEP 1: Settle this node's bounds completely
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 changed, restart evaluation
}
}
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 changed, restart evaluation
}
}
}
// STEP 2: Wake up neighbors (Push ONLY, no while loops)
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;
}
