#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using paira = array<int, 2>;
using ll = long long;
/*
We need to know-
Each vertices' components - To do this in O(1), we need to implement DSU
The count of "no" edges between components
When will we be merging? Exactly when there are |c_u| * |c_j| - 1 "no" edges between two components
*/
int N = 2;
vector<vector<int>> edges(N, vector<int>(N)); // # of NO edges between components
// dsu stuff
vector<int> parent(N);
vector<int> asize(N, 0);
void new_compo(int x) {
parent[x] = x;
asize[x] = 1;
}
int get_compo(int x) {
if (parent[x] == x) return x;
return parent[x] = get_compo(parent[x]);
}
void union_compo(int x, int y) {
x = get_compo(x);
y = get_compo(y);
if (x != y) {
if (asize[x] < asize[y]) swap(x, y);
parent[y] = x;
asize[x] += asize[y];
}
}
void initialize(int n) {
N = n;
edges.resize(N);
for (int i = 0; i < N; i++) {
edges[i].resize(N);
};
parent.resize(N);
asize.resize(N);
for (int i = 0; i < N; i++) {
new_compo(i);
}
}
int hasEdge(int u, int v) {
if (u > v) swap(u, v);
int cu = get_compo(u);
int cv = get_compo(v);
if (cu == cv) {
return 1;
}
// cout << size[cu] << ' ' << size[cv] << '\n';
if (asize[cu] < asize[cv]) swap(cu, cv);
if (edges[cv][cu] == 1LL*asize[cu]*asize[cv] - 1) {
// We must answer YES now
// cv chotota
// chototar parent hobe borota
// chotota deleted
// cv deleted
union_compo(cu, cv);
for (int i = 0; i < N; i++) {
if (i == cu || i == cv) continue;
edges[min(cu, i)][max(cu, i)] += edges[min(cv, i)][max(i, cv)];
return 1;
}
}
edges[cu][cv]++;
return 0;
}
