#include "game.h"
#include <bits/stdc++.h>
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#define ifdeb if(true)
#else
#define D(x) ;
#define ifdeb if(false)
#endif
#define all(x) begin(x), end(x)
using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;
int n;
int nam[1500][1500];
int vis[1500][1500];
int uf[1500];
int us[1500];
int root(int x) {
if(uf[x] == uf[uf[x]]) return uf[x];
uf[x] = root(uf[x]);
return uf[x];
}
void initialize(int N) {
n = N;
for(int i = 0; i < n; ++i) uf[i] = i;
for(int i = 0; i < n; ++i) us[i] = 1;
}
int hasEdge(int u, int v) {
int ru = root(u);
int rv = root(v);
int res = 0;
if(vis[u][v]) {
res = vis[u][v]-1;
} else if(ru == rv) {
res = 1;
} else if(nam[ru][rv]+1 == us[ru]*us[rv]) {
res = 1;
uf[ru] = rv;
us[rv] += us[ru];
for(int i = 0; i < n; ++i) {
nam[rv][i] += nam[ru][i];
nam[i][rv] = nam[rv][i];
}
} else {
res = 0;
nam[ru][rv] += 1;
nam[rv][ru] += 1;
}
vis[u][v] = res+1;
return res;
}
