#include "game.h"
#include <bits/stdc++.h>
using namespace std;
class DSU {
private:
vector<int> p, rank;
public:
DSU(int n) {
p.assign(n, -1);
rank.assign(n, 0);
}
int root(int x) {
if (p[x] < 0) {
return x;
}
return (p[x] = root(p[x]));
}
int sameSet(int x, int y) {
return (root(x) == root(y));
}
void connect(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (rank[x] > rank[y]) {
p[y] = x;
} else {
p[x] = y;
if (rank[x] == rank[y]) {
rank[y]++;
}
}
}
}
};
DSU dsu(0);
vector< vector<int> > cnt;
void initialize(int n) {
dsu = DSU(n);
cnt.assign(n, vector<int>(n, 1));
}
int hasEdge(int u, int v) {
if (dsu.sameSet(u, v)) {
return 0;
}
u = dsu.root(u);
v = dsu.root(v);
if (cnt[u][v] == 1) {
dsu.connect(u, v);
for (int i = 0; i < (int) cnt.size(); i++) {
if (dsu.sameSet(i, u)) {
continue;
}
if (dsu.root(u) == v) {
cnt[v][i] += cnt[u][i];
cnt[i][v] += cnt[i][u];
} else {
cnt[u][i] += cnt[v][i];
cnt[i][u] += cnt[i][v];
}
}
return 1;
}
cnt[u][v]--;
cnt[v][u]--;
return 0;
}
