#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector< int > U;
int getParents(int a){
if(U[a] == a) return a;
return U[a] = getParents(U[a]);
}
void Union(int a, int b){
U[getParents(a)] = getParents(b);
}
int N;
vector< int > S;
vector< vector< int> > badEdge;
void initialize(int n){
N = n;
U.resize(n);
badEdge.resize(n,vector<int>(n,0));
for(int i = 0; i < n; i++) U[i] = i;
S.resize(n,1);
}
int hasEdge(int u, int v) {
int a = getParents(u);
int b = getParents(v);
if(S[a]*S[b]-1 == badEdge[a][b]){
S[b] += S[a];
for(int i = 0; i < N; i++){
badEdge[b][i] += badEdge[a][i];
badEdge[i][b] += badEdge[i][a];
}
Union(a,b);
return 1;
}
badEdge[a][b]++, badEdge[b][a]++;
return 0;
}
/*
signed main(){
int n;
cin >> n;
initialize(n);
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
cout << i << ' ' << j << ' ' << hasEdge(i,j) << endl;
}
}
}
*/
