#include<bits/stdc++.h>
#include"game.h"
using namespace std;
typedef long long ll;
struct DSU{
vector<int> parent, size;
int N;
DSU(int n) : N(n){
parent.resize(N);
iota(parent.begin(), parent.end(), 0);
size.resize(N, 1);
}
void reset(){
size.assign(N, 1);
iota(parent.begin(), parent.end(), 0);
}
int find(int v){
return parent[v] = (parent[v]==v?v:find(parent[v]));
}
void merge(int v, int u){
if(size[find(v)] < size[find(u)])
swap(u, v);
size[find(v)]+= size[find(u)];
parent[find(u)] = find(v);
}
};
const int maxn = 1500;
int n;
vector<vector<int>> S(maxn+5, vector<int>(maxn+5));
DSU dsu(maxn+5);
void initialize(int k){
n = k;
dsu.reset();
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
S[i][j] = (i!=j);
}
int hasEdge(int v, int u){
if(dsu.find(v) == dsu.find(u)){
return 0;
} else if(S[dsu.find(v)][dsu.find(u)] == 1){
vector<int> sums(n);
for(int x = 0; x < n; x++)
sums[dsu.find(x)] = S[dsu.find(x)][dsu.find(v)]+S[dsu.find(x)][dsu.find(u)];
dsu.merge(u, v);
for(int x = 0; x < n; x++)
S[dsu.find(x)][dsu.find(v)] = S[dsu.find(v)][dsu.find(x)] = sums[dsu.find(x)];
return 1;
} else{
S[dsu.find(v)][dsu.find(u)]--;
S[dsu.find(u)][dsu.find(v)]--;
return 0;
}
}
