#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 5e5 + 5;
int n, k, mx[MX], mn[MX], tl[MX], tr[MX], ptl[MX], ptr[MX];
vector<int> Gf[MX], Gr[MX];
bool ans;
deque<int> todo;
bool inq[MX];
void check(int v) {
if (ans) return;
if (tl[v] >= tr[v]) {
ans = true;
return;
}
if (tr[v] - tl[v] <= (ptr[v] - ptl[v]) / 2 && !inq[v]) {
inq[v] = true;
todo.push_back(v);
}
}
void process() {
while (!todo.empty() && !ans) {
int v = todo.front();
todo.pop_front();
inq[v] = false;
if (tl[v] >= tr[v]) {
ans = true;
return;
}
if (tr[v] - tl[v] > (ptr[v] - ptl[v]) / 2)
continue;
ptl[v] = tl[v], ptr[v] = tr[v];
for (int w : Gf[v])
if (tl[v] > tl[w]) {
tl[w] = tl[v], check(w);
if (ans)
return;
}
for (int w : Gr[v])
if (tr[v] < tr[w]) {
tr[w] = tr[v], check(w);
if (ans)
return;
}
}
}
void init(int n_, int k_) {
n = n_, k = k_, ans = false;
todo.clear();
for (int i = 0; i < n; i++)
Gf[i].clear(), Gr[i].clear(), inq[i] = false;
for (int i = k; i < n; i++) {
mx[i] = tl[i] = ptl[i] = -1;
mn[i] = tr[i] = ptr[i] = k;
}
}
int add_teleporter(int u, int v) {
if (ans) return 1;
if (u < k && v < k) {
if (u >= v)
ans = true;
return ans;
}
if (u < k) {
mx[v] = max(mx[v], u);
if (u > tl[v])
tl[v] = u, check(v);
} else if (v < k) {
mn[u] = min(mn[u], v);
if (v < tr[u])
tr[u] = v, check(u);
} else {
Gf[u].push_back(v);
Gr[v].push_back(u);
if (tl[u] > tl[v])
tl[v] = tl[u], check(v);
if (tr[v] < tr[u])
tr[u] = tr[v], check(u);
}
process();
return ans;
}
