#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=707;
vector <int> ke[300001][4],ve;
int dp[300001][2],a[300001][2],n,k,cnt;
void init(int N, int K) {
n=N;
k=K;
for (int i=0;i<n;i++){
a[i][0]=(i<k?i:n+1);
a[i][1]=(i<k?i:-2);
}
memset(dp,-1,sizeof(dp));
}
int f(int u, int i){
if (dp[u][i]!=-1)
return dp[u][i];
ve.push_back(u);
dp[u][i]=a[u][i];
for (int v:ke[u][i+2])
dp[u][i]=(i?max(dp[u][i],f(v,i)):min(dp[u][i],f(v,i)));
return dp[u][i];
}
void dfs(int u, int i, int s){
if (a[u][i]!=-2&&a[u][i]!=n+1)
return;
a[u][i]=s;
for (int v:ke[u][i^1])
dfs(v,i,s);
}
void reset(){
for (int i=0;i<n;i++){
ke[i][0].insert(ke[i][0].end(),ke[i][2].begin(),ke[i][2].end());
ke[i][2].clear();
ke[i][1].insert(ke[i][1].end(),ke[i][3].begin(),ke[i][3].end());
ke[i][3].clear();
}
for (int i=0;i<n;i++){
a[i][0]=n+1;
a[i][1]=-2;
}
for (int i=0;i<k;i++)
dfs(i,0,i);
for (int i=k-1;i>=0;i--)
dfs(i,1,i);
}
int add_teleporter(int u, int v) {
cnt++;
if (cnt%sz==0)
reset();
for (int i:ve)
dp[i][0]=dp[i][1]=-1;
ve.clear();
ke[u][2].push_back(v);
ke[v][3].push_back(u);
int a=f(u,1),b=f(v,0);
if (a<0||a>=n||b<0||b>=n)
return 0;
return (a>=b);
}
