#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
vector<int> free_e;
vector<short> free_c;
vector<char> edges;
int n;
void initialize(int n_) {
n = n_;
free_c.resize(n,n-1);
free_e.resize(n,(n)*(n-1)/2);
for (int i = 0; i < n; i++) free_e[i] -= i;
edges.resize(n*n, 0);
}
void dc(int x, int y) {
while (true) {
free_e[x] -= y;
if (--free_c[x] != 1) return;
y = x;
x = free_e[x];
edges[max(x,y)+min(x,y)*n] = 1;
}
}
int hasEdge(int u, int v) {
if (edges[max(u,v)+min(u,v)*n]) return true;
free_e[v] -= u;
free_c[v]--;
dc(u,v);
free_c[v]++;
free_e[v] += u;
dc(v,u);
return false;
}
