#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;
for(int i = 0; i < n; i++) {
l[i] = -1;
r[i] = k;
in_q[i] = false;
g[i].clear();
rg[i].clear();
}
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) {
if(v <= u && max(u, v) < k) return 1;
if(max(u, v) < k) return 0;
// 1. Immediate edge cycle check
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;
g[u].push_back(v);
rg[v].push_back(u);
queue<int> q;
// 2. Initial Pushes (Only push if the node isn't "dead" i.e., l <= r)
if (v >= k && l[v] <= r[v] && (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] && (l[u] + r[u]) / 2 >= min_out_v && !in_q[u]) {
q.push(u);
in_q[u] = true;
}
while(!q.empty()){
int node = q.front();
q.pop();
in_q[node] = false;
// If the node is completely resolved, skip evaluation
if (l[node] > r[node]) continue;
bool changed = true;
while(changed && l[node] <= r[node]) {
changed = false;
int mid = (l[node] + r[node]) / 2;
// Check incoming edges
for(int p : rg[node]){
int max_in_p = (p >= k) ? l[p] - 1 : p;
if(max_in_p >= mid) {
if (l[node] < mid + 1) { // Only update if it actually grows L
l[node] = mid + 1;
if (l[node] > r[node] + 1) return 1; // Strict Cycle Check
changed = true;
break;
}
}
}
// Check outgoing edges (Notice no 'continue' here, evaluate SAME mid!)
for(int nx : g[node]){
int min_out_nx = (nx >= k) ? r[nx] + 1 : nx;
if(min_out_nx <= mid) {
if (r[node] > mid - 1) { // Only update if it actually shrinks R
r[node] = mid - 1;
if (l[node] > r[node] + 1) return 1; // Strict Cycle Check
changed = true;
break;
}
}
}
}
// 3. Wake up neighbors (only if they aren't dead)
for(int nx : g[node]){
if(nx >= k && l[nx] <= r[nx] && (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] && (l[p] + r[p]) / 2 >= r[node] + 1 && !in_q[p]){
q.push(p);
in_q[p] = true;
}
}
}
return 0;
}
