#include "game.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 300030;
int n, k, ok;
vector<int> adj[MAXN], rev[MAXN];
int mx[MAXN]; // max special that can reach i
int mn[MAXN]; // min special that i can reach
void init(int _n, int _k) {
n = _n; k = _k;
ok = 0;
For(i, 0, n - 1) {
adj[i].clear();
rev[i].clear();
mx[i] = -1;
mn[i] = n + 1;
}
For(i, 0, k - 2) {
mx[i + 1] = i;
mn[i] = i + 1;
adj[i].eb(i + 1);
rev[i + 1].eb(i);
}
}
void dfs_mx(int x, int m) {
if(mx[x] >= m) return;
mx[x] = m;
if(mx[x] >= mn[x]) {
ok = 1; return;
}
for(auto &i:adj[x]) {
dfs_mx(i, m);
}
}
void dfs_mn(int x, int m) {
if(mn[x] <= m) return;
mn[x] = m;
if(mx[x] >= mn[x]) {
ok = 1; return;
}
for(auto &i:rev[x]) {
dfs_mn(i, m);
}
}
int add_teleporter(int u, int v) {
if(u < k && v < k) {
if(u >= v) return 1;
return 0;
}
adj[u].eb(v);
rev[v].eb(u);
if(u < k) {
dfs_mx(v, u);
dfs_mn(u, mn[v]);
} else if(v < k) {
dfs_mx(v, mx[u]);
dfs_mn(u, v);
} else {
dfs_mx(v, mx[u]);
dfs_mn(u, mn[v]);
}
// cout << "mx:";
// For(i, 0, n - 1) cout << " " << mx[i];
// cout << "\n";
// cout << "mn:";
// For(i, 0, n - 1) cout << " " << mn[i];
// cout << "\n";
return ok;
}
/*
4
0
2
*/
