#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/ioi14_d1/debug.h"
#else
#define debug(...) void(37)
#endif
template<typename T>
vector<T> inverse_fuck(T* a, int N) {
vector<T> res(N);
for (int i = 0; i < N; ++i) {
res[i] = a[i];
}
return res;
}
template<typename T>
T* fuck(vector<T> a) {
T res[int(a.size())];
for (int i = 0; i < int(a.size()); ++i) {
res[i] = a[i];
}
return res;
}
struct DSU {
vector<int> link;
vector<int> size;
DSU() { }
DSU(int n) {
link.resize(n);
size.resize(n, 1);
iota(link.begin(), link.end(), 0);
}
int get(int x) {
return link[x] = (x == link[x] ? x : get(link[x]));
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) {
return false;
}
link[y] = x;
size[x] += size[y];
return true;
}
};
int n;
vector<vector<int>> deg;
DSU d;
void initialize(int _n) {
n = _n;
deg.resize(n, vector<int>(n));
d = DSU(n);
}
int hasEdge(int u, int v) {
debug(u, v);
u = d.get(u), v = d.get(v);
assert(u != v);
int need = d.size[u] * d.size[v] - 1;
int has = max(deg[v][u], deg[u][v]);
debug(need, has);
if (has == need) {
d.unite(v, u);
vector<int> next(n);
for (int i = 0; i < n; ++i) {
int to = d.get(i);
next[to] += deg[v][i] + deg[u][i];
}
swap(deg[v], next);
return true;
} else {
deg[v][u] += 1;
deg[u][v] += 1;
return false;
}
}
