#include "game.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#include <bitset>
typedef long long llong;
const int MAXN = 5000 + 10;
int n;
struct DSU
{
int par[MAXN];
int dep[MAXN];
std::bitset <MAXN> isPresent[MAXN];
void build()
{
std::iota(par + 1, par + 1 + n, 1);
std::fill(dep + 1, dep + 1 + n, 1);
for (int i = 1 ; i <= n ; ++i)
{
isPresent[i].set();
}
}
int find(int node)
{
if (par[node] == node)
{
return node;
}
return par[node] = find(par[node]);
}
void connect(int u, int v)
{
u = find(u);
v = find(v);
if (dep[u] < dep[v])
{
std::swap(u, v);
}
if (dep[u] == dep[v])
{
dep[v]++;
}
par[u] = v;
for (int i = 1 ; i <= n ; ++i)
{
if (isPresent[u][i])
{
isPresent[i][u] = 0;
isPresent[i][v] = 1;
}
}
for (int i = 1 ; i <= n ; ++i)
{
if (isPresent[u][i])
{
isPresent[v][i] = 1;
}
}
isPresent[v][u] = 0;
}
};
DSU dsu;
std::bitset <MAXN> vis;
bool dfs(int node, int v)
{
if (node == v || dsu.isPresent[node][v])
{
return true;
}
vis[node] = true;
std::bitset <MAXN> bs = dsu.isPresent[node] ^ (dsu.isPresent[node] & vis);
while (bs.count() > 0)
{
int first = bs._Find_first();
if (!vis[first])
{
if (dfs(first, v))
{
return true;
}
bs ^= (bs & vis);
}
}
return false;
}
void initialize(int N)
{
n = N;
dsu.build();
}
int hasEdge(int u, int v)
{
u++; v++;
u = dsu.find(u);
v = dsu.find(v);
dsu.isPresent[u][v] = 0;
dsu.isPresent[v][u] = 0;
vis.reset();
if (dfs(u, v))
{
return 0;
}
dsu.connect(u, v);
return 1;
}
