#include "game.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int n, k;
vector<vector<int>> edge, revedge;
vector<int> maxin, minout;
}
void init(int _n, int _k) {
n = _n, k = _k;
edge = revedge = vector<vector<int>>(n);
maxin = vector<int>(n, -1);
minout = vector<int>(n, k+1);
}
bool return_value = false;
void propagate_max(int u) {
for (int v : edge[u]) {
if (maxin[v] < maxin[u] && v >= k) {
maxin[v] = maxin[u];
if (maxin[v] >= minout[v]) return_value = true;
propagate_max(v);
}
}
}
void propagate_min(int u) {
for (int v : revedge[u]) {
if (minout[v] > minout[u] && v >= k) {
minout[v] = minout[u];
if (maxin[v] >= minout[v]) return_value = true;
propagate_min(v);
}
}
}
int add_teleporter(int u, int v) {
if (u < k && v < k) {
if (v <= u) return 1;
return 0;
}
edge[u].push_back(v);
revedge[v].push_back(u);
if (u < k) {
maxin[v] = max(maxin[v], u);
} else {
maxin[v] = max(maxin[v], maxin[u]);
}
if (v < k) {
minout[u] = min(minout[u], v);
} else {
minout[u] = min(minout[u], minout[v]);
}
propagate_min(u);
propagate_max(v);
if (maxin[u] >= minout[u]) return_value = true;
if (maxin[v] >= minout[v]) return_value = true;
return return_value;
}
