#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 300005;
int N, K, A[mxN], B[mxN];
vt<int> adj[mxN], radj[mxN];
void init(int n, int k) {
N = n, K = k;
fill(A, A + N, -1);
fill(B, B + N, N);
}
int dfs1(const int i) {
if (A[i] >= B[i])
return 1;
for (const auto &j : adj[i]) {
if (A[i] <= A[j])
continue;
A[j] = A[i];
if (dfs1(j))
return 1;
}
return 0;
}
int dfs2(const int i) {
if (A[i] >= B[i])
return 1;
for (const auto &j : radj[i]) {
if (B[i] >= B[j])
continue;
B[j] = B[i];
if (dfs2(j))
return 1;
}
return 0;
}
int add_teleporter(int u, int v) {
if (u < K && v < K)
return u >= v;
if (u < K) {
if (A[v] >= u)
return 0;
A[v] = u;
return dfs1(v);
}
if (v < K) {
if (B[u] <= v)
return 0;
B[u] = v;
return dfs2(v);
}
if (u == v)
return 0;
adj[u].push_back(v);
radj[v].push_back(u);
return dfs1(u) || dfs2(v);
}
