#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1505;
#define pii pair<int,int>
#define fs first
#define sc second
int n;
struct DSU{
int dsu[mxn];
int paths[mxn][mxn];
void init(int n){
for(int i = 0;i<n;i++)dsu[i] = i;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(i == j)continue;
paths[i][j] = paths[j][i] = 1;
}
}
return;
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
paths[a][b] --;paths[b][a]--;
a = root(a),b = root(b);
if(a == b)return;
dsu[b] = a;
for(int i = 0;i<n;i++)paths[a][i] += paths[b][i];
for(int i = 0;i<n;i++)paths[i][a] += paths[b][i];
return;
}
};
DSU dsu;
void initialize(int nn) {
n = nn;
dsu.init(n);
}
int hasEdge(int u, int v) {
u = dsu.root(u),v = dsu.root(v);
if(dsu.paths[u][v] != 1){
dsu.paths[u][v]--;
dsu.paths[v][u]--;
return 0;
}
dsu.onion(u,v);
return 1;
}
