#include "game.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using vi = vector<ll>;
struct dsu {
vi r, p;
gp_hash_table<int, int> cnt[1500];
void init(int n) {
r.resize(n+1);
p.resize(n+1);
for(int i = 0; i <= n; i++) p[i] = i;
}
int par(int i) {
if(i == p[i]) return i;
return p[i] = par(p[i]);
}
void unite(int u, int v) {
u=par(u),v=par(v);
if(u==v) return;
if(r[u]<r[v]) swap(u, v);
p[v] = u;
r[u] += r[u]==r[v];
for(auto i : cnt[v])
cnt[u][i.first] += i.second;
cnt[v].clear();
}
};
#define left afsjlk
dsu x;
set<pair<int, int>> left;
int n;
void initialize(int N) {
n=N;
x.init(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
x.cnt[i][j]++;
}
void upd() {
for(int i = 0; i < n; i++) {
if(x.cnt[i].empty()) continue;
gp_hash_table<int, int> t;
for(auto j : x.cnt[i])
t[x.par(j.first)]+=j.second;
swap(t, x.cnt[i]);
}
}
int hasEdge(int u, int v) {
if(u>v)swap(u, v);
if((u=x.par(u))==(v=x.par(v)))
return 1;
//cout << x.cnt[u][v] << '\n';
int t = x.cnt[u][v];x.cnt[u][v]--, x.cnt[v][u]--;
if(t==1) x.unite(u, v), upd();
return t==1;
}
