#include "game.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<vector<int>> edge;
vector<vector<int>> invedge;
vector<int> r;
vector<int> s;
int n,k;
void init(int _n, int _k) {
n=_n;
k=_k;
edge.resize(n);
invedge.resize(n);
r.resize(n,-1);
s.resize(n,1e9);
for (int i = 0; i < k-1; i++)
{
edge[i].push_back(i+1);
invedge[i+1].push_back(i);
r[i]=s[i]=i;
r[i+1]=s[i+1]=i+1;
}
}
bool rdfs(int x, int v){
if(v>=s[x]) return true;
if(r[x]>=v) return false;
r[x]=v;
for (auto u : edge[x])
if(rdfs(u,v)) return true;
return false;
}
bool sdfs(int x, int v){
if(r[x]>=v) return true;
if(s[x]<=v) return false;
s[x]=v;
for (auto u : invedge[x])
if(sdfs(u,v)) return true;
return false;
}
int add_teleporter(int u, int v) {
bool b=false;
edge[u].push_back(v);
invedge[v].push_back(u);
if(rdfs(v,r[u])) b=true;
if(sdfs(u,s[v])) b=true;
return (int)b;
}
