#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int n,p[1501],r[1501],com,cnt[1501],s,sz[1501];
int find(int x) {
while (x!=p[x]) x=p[x];
return x;
}
void unite(int x, int y) {
x=find(x); y=find(y);
if (r[x]<r[y]) swap(x,y);
p[y]=x;
sz[x]+=sz[y];
cnt[x]+=cnt[y];
if (r[x]==r[y])++r[x];
--com;
}
void initialize(int N) {
n=N; com=N;
for (int i=0; i<n; ++i) p[i]=i,sz[i]=1;
}
int hasEdge(int u, int v) {
++s;
u=find(u); v=find(v);
if (u==v) return 1;
if (cnt[u]<(n-sz[u])*sz[u]-1 && cnt[v]<(n-sz[v])*sz[v]-1 && com<=n*(n-1)/2+1-s) {
++cnt[u];
++cnt[v];
return 0;
} else {
unite(u,v);
return 1;
}
}
