#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ld long double
bool p[1600][1600];
unordered_map<int,int> arc[170];
int rad,N;
int hasEdge(int u, int v) {
int ga=u/rad,gb=v/rad;
if(ga==gb){
p[u][v]=0;
p[v][u]=1;
vector<bool> vis(rad+2,0);
queue<int> q;
q.push(u);
while(!q.empty()){
int pos=q.front();
q.pop();
if(pos/rad!=ga)continue;
if(vis[pos%rad])continue;
vis[pos%rad]=1;
for(int i=rad*ga;i<rad*(ga+1);i++){
if(i>=N)break;
if(p[pos][i])q.push(i);
}
}
bool ok=1;
for(int i=0;i<rad;i++){
if(ga*rad+i>=N)break;
if(vis[i]==0){
ok=0;
break;
}
}
if(ok==0){
p[u][v]=1;
p[v][u]=1;
return 1;
}
return 0;
}
p[u][v]=0;
p[v][u]=0;
arc[ga][gb]--;
arc[gb][ga]--;
bool ok=0;
if(arc[ga][gb]>0)ok=1;
else{
arc[ga].erase(gb);
arc[gb].erase(ga);
}
vector<bool> vis(N/rad+2,0);
queue<int> q;
q.push(ga);
while(!q.empty() && ok==0){
int pos=q.front();
q.pop();
if(pos==gb){
ok=1;
break;
}
if(vis[pos])continue;
vis[pos]=1;
for(auto &[k,_]:arc[pos]){
if(k==gb){
ok=1;
break;
}
if(vis[k]==0)q.push(k);
}
}
if(ok==0){
p[u][v]=1;
p[v][u]=1;
arc[ga][gb]=1;
arc[gb][ga]=1;
return 1;
}
return 0;
}
void initialize(int n){
rad=min(15,n);
N=n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
p[i][j]=1;
arc[i/rad][j/rad]++;
}
}
}
