#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAXN = 1500;
int sef[MAXN], nrm[MAXN][MAXN];
int n;
//O(n^2)
//o sa zic nu la fiecare muchie, mai putin daca e ultima muchie care are capetele in acele 2 componente conexe
//deci o sa zic da de n - 1 ori, doar atunci cand trebuie neaparat sa unesc componentele
//o sa fac dsu brut ca sunt n^2 queryuri si n updateuri
//as fi putut sa fac si dsu normal cu small to large
void initialize(int nr) {
int i, j;
n = nr;
for (i = 0; i < n; i++) {
sef[i] = i;
for (j = i + 1; j < n; j++) {
nrm[i][j] = nrm[j][i] = 1;
}
}
}
int hasEdge(int x, int y) {
int i, a, b;
//nu au cum sa fie din aceeasi componenta ca altfel nu le-as fi unit inca
a = sef[x];
b = sef[y];
nrm[a][b]--;
nrm[b][a]--;
if (nrm[a][b] == 0) {//este ultima muchie, deci le unesc
for (i = 0; i < n; i++) {
if (sef[i] == a) {
sef[i] = b;
}
}
//muchiile de la componenta lui a sunt acum de la componenta lui b
for (i = 0; i < n; i++) {
nrm[b][i] += nrm[a][i];
nrm[i][b] += nrm[a][i];
}
return 1;
}
return 0;
}
