#include "game.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#pragma GCC optimize ("Ofast")
typedef long long llong;
const int MAXN = 5000 + 10;
int n;
int d[MAXN];
struct DSU
{
int par[MAXN];
int dep[MAXN];
bool isPresent[MAXN][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)
{
std::fill(isPresent[i] + 1, isPresent[i] + 1 + n, 1);
}
}
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;
d[v] = 0;
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)
{
isPresent[v][i] |= isPresent[u][i];
d[v] += isPresent[v][i];
}
d[v] -= isPresent[v][u];
isPresent[v][u] = false;
}
};
DSU dsu;
bool vis[MAXN];
bool dfs(int node, int v)
{
if (node == v || dsu.isPresent[node][v])
{
return true;
}
vis[node] = true;
for (int u = 1 ; u <= n ; ++u)
{
if (vis[u] || !dsu.isPresent[node][u])
{
continue;
}
if (dfs(u, v))
{
return true;
}
}
return false;
}
void initialize(int N)
{
n = N;
dsu.build();
for (int i = 1 ; i <= n ; ++i)
{
d[i] = n - 1;
}
}
int cntRemoved = 0;
int hasEdge(int u, int v)
{
u++; v++;
u = dsu.find(u);
v = dsu.find(v);
std::fill(vis + 1, vis + 1 + n, false);
dsu.isPresent[u][v] = false;
dsu.isPresent[v][u] = false;
cntRemoved++;
if (d[u] > 1 && d[v] > 1 && (cntRemoved < d[u] * d[v] || dfs(u, v)))
{
d[u]--;
d[v]--;
return 0;
}
cntRemoved--;
dsu.connect(u, v);
return 1;
}
