#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;
void push_it_for(ll node, ll ind) {
pref[node] = ind;
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;
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] >= suf[v]) { return 1; }
if (pref[u] >= pref[v]) {
push_it_for(v, pref[u]);
}
if (suf[v] <= suf[u]) {
push_it_back(u, suf[v]);
}
return 0;
}
/*
#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 s;
vll vis;
ll sz = 0;
bool got_it = false;
void dfs(ll node) {
vis[node] = true;
for (auto i : g[node]) {
if (vis[i]) { continue; }
dfs(i);
}
s.push_back(node);
}
void dfs_tran(ll node) {
if (node < k) { got_it = true; }
sz++;
vis[node] = true;
for (auto i : g_tran[node]) {
if (vis[i]) { continue; }
dfs_tran(i);
}
}
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);
}
}
int add_teleporter(int u, int v) {
g[u].push_back(v);
g_tran[v].push_back(u);
vis.clear();
vis.resize(n);
s.clear();
for (ll i = 0; i < n; i++) {
if (!vis[i]) { dfs(i); }
}
vis.clear();
vis.resize(n);
for (ll i = n - 1; i >= 0; i--) {
if (!vis[s[i]]) {
sz = 0, got_it = false;
dfs_tran(s[i]);
if (sz > 1 && got_it) {
return 1;
}
}
}
for (ll i = 0; i < k; i++) {
for (auto j : g[i]) {
if (j == i) {
return 1;
}
}
}
return 0;
}*/
