#include <bits/stdc++.h>
using namespace std;
#include "game.h"
#define pii pair<int,int>
#define ff first
#define ss second
vector<vector<int>> in,out;
vector<vector<int>> g,rev;
vector<int> lyr;
vector<int> par;
int n,k;
bool dobr(int cur,int m){
int p = par[m];
if(p==-1)return true;
int ll = lyr[p];
if(m>p)return out[ll][cur]==p;
else return in[ll][cur]==p;
}
int cnt = 0;
bool dfs(int cur,int l,int r);
bool rfs(int cur,int l,int r);
bool addvertex(int x,int l,int r)
{
cnt++;
if(l>r)return 0;
int m=l+r>>1;
int ll = lyr[m];
if(x==m)return 1;
int bad = 0;
for(int a:rev[x])
if(a==m||out[ll][a]==m)
{
bad=max<int>(bad,dfs(x,l,r));
break;
}
for(int a:g[x])
if(a==m||in[ll][a]==m)
{
bad=max<int>(bad,rfs(x,l,r));
break;
}
return bad;
}
bool dfs(int cur,int l,int r)
{
cnt++;
int m = l+r>>1;
int ll = lyr[m];
if (cur == m || in[ll][cur]==m)
return 1;
if (out[ll][cur]==m || !dobr(cur,m))
return 0;
out[ll][cur]=m;
for (int a : g[cur])
if(dfs(a,l,r))return 1;
if(addvertex(cur,m+1,r))return 1;
return 0;
}
bool rfs(int cur,int l,int r)
{
cnt++;
int m = l+r>>1;
int ll = lyr[m];
if (cur == m || out[ll][cur]==m)
return 1;
if (in[ll][cur]==m || !dobr(cur,m))
return 0;
in[ll][cur]=m;
for (int a : rev[cur])
if(rfs(a,l,r))return 1;
if(addvertex(cur,l,m-1))return 1;
return 0;
}
const int lgk = 18;
void init(int N,int K) {
n = N,k = K;
in.clear();
out.clear();g.clear();rev.clear();
in.resize(lgk,vector<int>(n,-1));
lyr.resize(n,0);
out =in;
g.resize(n),rev.resize(n);
par.resize(k,-1);
for(int i = 0; i < k-1; i++)
{
g[i].push_back(i+1);
rev[i+1].push_back(i);
}
function<void(int,int,int,int)> rec = [&](int l,int r,int pr,int ll)
{
if(l>r)return;
int m = l+r>>1;
for(int i = m+1; i <= r; i++)
out[ll][i]=m;
for(int i = l; i < m; i++)
in[ll][i]=m;
lyr[m]=ll;
par[m]=pr;
rec(l,m-1,m,ll+1);
rec(m+1,r,m,ll+1);
};
rec(0,k-1,-1,0);
}
bool add(int u,int v,int l,int r)
{
if(l>r)return 0;
int m = l+r>>1;
int ll = lyr[m];
int ans = 0;
if(out[ll][u]==m&&out[ll][v]==m)
return add(u,v,m+1,r);
if(in[ll][u]==m&&in[ll][v]==m)
return add(u,v,l,m-1);
if((u==m||out[ll][u]==m)&&out[ll][v]!=m)
ans=max<int>(ans,addvertex(v,l,r));
if((v==m||in[ll][v]==m)&&in[ll][u]!=m)
ans=max<int>(ans,addvertex(u,l,r));
return ans;
}
int add_teleporter(int u, int v) {
if(u<k&&u==v)return 1;
g[u].push_back(v);
rev[v].push_back(u);
return add(u,v,0,k-1);
}
