#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector <int> par, sz;
int n;
inline void init(int _n) {
n = _n;
par.resize(n, -1), sz.resize(n, 1);
}
int root(int x) {
if(par[x] == -1)
return x;
return par[x] = root(par[x]);
}
inline void join(int x, int y) {
x = root(x), y = root(y);
if(x != y) {
par[x] = y;
sz[y] += sz[x];
}
}
}dsu;
static int N;
vector < vector <int> > cnt;
vector <int> vis;
int now;
void initialize(int n) {
N = n;
dsu.init(N); vis.resize(N);
cnt.resize(N, vector <int>(N));
}
int hasEdge(int u, int v) {
u = dsu.root(u), v = dsu.root(v);
if(u == v) {
return 0;
}
if(cnt[u][v] + 1 == dsu.sz[u] * dsu.sz[v]) {
now++;
for(int i = 0; i < N; i++) {
int cur = dsu.root(i);
if(vis[cur] == now) {
continue;
}
vis[cur] = now;
if(cur != u && cur != v) {
cnt[cur][v] += cnt[cur][u];
cnt[v][cur] += cnt[cur][u];
}
}
dsu.join(u, v);
return 1;
}
else {
cnt[u][v]++, cnt[v][u]++;
return 0;
}
}
