#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define pb push_back
#define fr first
#define se second
#define mp make_pair
using namespace std;
const int MAXN=1501;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
bool arb[MAXN][MAXN], vis[MAXN];
vector<ll>grafo[MAXN];
ll memo[MAXN][MAXN], N;
vector<pair<ll,ll>>ars;
void arm(ll nod)
{
vis[nod]=1;
for(auto i:grafo[nod])
{
if(!vis[i])
{
ars.pb({nod,i});
arb[nod][i]=arb[i][nod]=1;
arm(i);
}
}
}
ll vivas;
void initialize(int n) {
N=n;
vivas=(N*(N-1))/2;
ll i, j;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
if(i!=j)
grafo[i].pb(j);
memo[i][j]=-1;
}
arm(rng()%n);
}
bool isconex()
{
memset(vis,0,sizeof(vis));
vector<pair<ll,ll>>ant=ars;
for(auto k:ars)
arb[k.fr][k.se]=arb[k.se][k.fr]=0;
ars.resize(0);
arm(rng()%N);
for(ll i=0; i<N; i++)
if(!vis[i])
{
swap(ant,ars);
for(auto k:ars)
arb[k.fr][k.se]=arb[k.se][k.fr]=1;
return 0;
}
return 1;
}
void bor(ll u, ll v)
{
vector<ll>vec;
for(auto k:grafo[u])
if(k!=v)
vec.pb(k);
swap(vec,grafo[u]);
}
int hasEdge(int u, int v) {
if(vivas==N-1)
return 1;
if(u==v)
return 0;
if(memo[u][v]!=-1)
return memo[u][v];
bor(u,v);
bor(v,u);
if(!arb[u][v])
{
memo[u][v]=memo[v][u]=0;
vivas--;
return 0;
}
if(isconex())
{
memo[u][v]=memo[v][u]=0;
vivas--;
return 0;
}
grafo[u].pb(v);
grafo[v].pb(u);
memo[u][v]=memo[v][u]=1;
return 1;
}
