#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int n , k;
vector< int > mx , mn , l , r;
vector< vector< int > > g , g2;
bool fixNode(int node){
if(mx[node] >= mn[node])
return false;
int mid;
bool good = false;
while(l[node] < r[node]){
mid = (l[node] + r[node]) / 2;
if(mn[node] <= mid){
r[node] = mid;
good = true;
}
else if(mx[node] > mid){
l[node] = mid + 1;
good = true;
}
else
break;
}
return good;
}
void init(int n, int k) {
::n = n;
::k = k;
mx.resize(n , 0);
mn.resize(n , k + 1);
l.resize(n , 0);
r.resize(n , k + 1);
for(int i = 0 ;i < k;i++){
mn[i] = mx[i] = i + 1;
}
g.resize(n);
g2.resize(n);
}
void DFSMax(int node){
for(int i = 0 ;i < (int)g[node].size();i++){
if(g[node][i] < k){
mn[node] = min(mn[node] , g[node][i] + 1);
continue;
}
mx[g[node][i]] = max(mx[g[node][i]] , mx[node]);
if(fixNode(g[node][i])){
DFSMax(g[node][i]);
}
mn[node] = min(mn[node] , mn[g[node][i]]);
}
fixNode(node);
}
void DFSMin(int node){
for(int i = 0 ;i < (int)g2[node].size();i++){
if(g2[node][i] < k){
mx[node] = max(mx[node] , g2[node][i] + 1);
continue;
}
mn[g2[node][i]] = min(mn[g2[node][i]] , mn[node]);
if(fixNode(g2[node][i])){
DFSMin(g2[node][i]);
}
mx[node] = max(mx[node] , mx[g2[node][i]]);
}
fixNode(node);
}
int add_teleporter(int u, int v) {
if(u < k && v < k){
if(u >= v)
return 1;
return 0;
}
g[u].push_back(v);
g2[v].push_back(u);
//fix max
if(v >= k){
mx[v] = max(mx[v] , mx[u]);
if(fixNode(v)){
DFSMax(v);
DFSMin(v);
}
if(mx[v] >= mn[v])
return 1;
}
//fix min
if(u >= k){
mn[u] = min(mn[u] , mn[v]);
if(fixNode(u)){
DFSMin(u);
DFSMax(u);
}
if(mx[u] >= mn[u])
return 1;
}
return 0;
}
