#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// for each node store the latest special node it can be reached from (from[u])
// and the earliest special node it can reach (to[u])
// when connecting u and v such that to[v] <= from[u] answer is 1
vector<vector<int>> g, rev;
int n, k;
vector<int> from, to;
void init(int N, int K) {
n = N;
k = K;
g.clear();
rev.clear();
from.clear();
to.clear();
g.resize(n+1);
rev.resize(n+1);
from.assign(n+1, -1);
to.resize(n+1, n+1);
for (int i = 1; i <= k; i++) {
from[i] = i;
to[i] = i;
}
for (int i = 1; i < k; i++) {
g[i].push_back(i+1);
rev[i+1].push_back(i);
}
}
void set_to(int u, int val) {
if (to[u] <= val) return;
to[u] = val;
for (auto next: rev[u]) {
set_to(next, val);
}
}
void set_from(int u, int val) {
if (from[u] >= val) return;
from[u] = val;
for (auto next: g[u]) {
set_from(next, val);
}
}
int add_teleporter(int u, int v) {
u++;
v++;
if (to[v] <= from[u]) return 1;
if (u == v && u <= k) return 1;
if (u == v) return 0;
g[u].push_back(v);
rev[v].push_back(u);
set_to(u, to[v]);
set_from(v, from[u]);
//for (int i = 1; i <= n; i++) {
// cout << "DEB: " << to[i] << " " << from[i] << "\n";
//}
//cout << "\n";
return 0;
}
