#include <iostream>
#include <set>
#include "game.h"
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
using namespace std;
int dsu[1510], rnk[1510], n, cnt[1510][1510];
set<pii> svi;
int root(int u)
{
while (u!=dsu[u])
{
dsu[u]=dsu[dsu[u]];
u=dsu[u];
}
return u;
}
void connect(int ru, int rv)
{
//if (root(u)==root(v)) return;
if (rnk[ru]<=rnk[rv])
{
if (rnk[ru]==rnk[rv]) rnk[rv]++;
dsu[ru]=rv;
}
else
dsu[rv]=ru;
int r=root(ru);
int pr=ru+rv-r;
///cout<<ru<<"+"<<rv<<"->"<<r<<endl;
for (int i=0; i<n; i++) {
cnt[i][r]+=cnt[i][pr];
cnt[r][i]+=cnt[i][pr];
}
}
void initialize(int N) {
n=N;
for (int i=0; i<n; i++) for (int j=0; j<n; j++) { if (i<j) svi.insert({i, j}); cnt[i][j]=1; }
for (int i=0; i<n; i++) { dsu[i]=i; rnk[i]=1; }
}
void out()
{
for (int i=0; i<n; i++) { for (int j=0; j<n; j++) if (i!=j) cout<<cnt[i][j]<<" "; else cout<<-1<<" "; cout<<endl; }
}
int hasEdge(int u, int v) {
if (u>v) swap(u, v);
int ru, rv; ru=root(u); rv=root(v);
if (ru==rv) return 1;
if (cnt[ru][rv]>1)
{
cnt[ru][rv]--;
cnt[rv][ru]--;
return 0;
}
else
{
connect(ru, rv);
//out();
return 1;
}
/*svi.erase({u, v});
bool moze=true;
for (auto par:svi)
{
int a, b; a=par.xx; b=par.yy;
//cout<<a<<" "<<b<<" "<<root(a)<<" "<<root(b)<<" "<<ru<<" "<<rv<<endl;
if ((root(a)==ru && root(b)==rv) || (root(a)==rv && root(b)==ru)) { moze=false; break; }
}
if (!moze) return 0;
connect(u, v);
return 1;*/
}
