#include "game.h"
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iomanip>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
ll n, k;
vvll g, g_tran;
vll pref, suf;
bool got = false;
void push_it_for(ll node, ll ind) {
pref[node] = ind;
if (pref[node] >= suf[node]) { got = true; }
for (auto i : g[node]) {
if (pref[i] < ind) {
push_it_for(i, ind);
}
}
}
void push_it_back(ll node, ll ind) {
suf[node] = ind;
if (pref[node] >= suf[node]) { got = true; }
for (auto i : g_tran[node]) {
if (suf[i] > ind) {
push_it_back(i, ind);
}
}
}
void init(int N, int K) {
n = N, k = K;
g.resize(n);
g_tran.resize(n);
for (ll i = 0; i < k -1; i++) {
g[i].push_back(i + 1);
g_tran[i + 1].push_back(i);
}
pref.resize(n, -1);
suf.resize(n, k);
for (ll i = 0; i < k; i++) {
pref[i] = i, suf[i] = i;
}
}
int add_teleporter(int u, int v) {
g[u].push_back(v);
g_tran[v].push_back(u);
if (pref[u] < pref[v]) {
push_it_for(v, pref[u]);
}
if (suf[v] > suf[u]) {
push_it_back(u, suf[v]);
}
if (got) {
return 1;
}
return 0;
}
