#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
int pairing[1501][1501];
int expectedSize[5001] = {0};
int currSize[5001] = {0};
void initialize(int n) {
int cp = 0;
for(int l = 1; l <= n; l <<= 1) {
for(int i = 1; i + l <= n; i += l+l) {
// [i, i+l-1] and [i+l, i+l+l-1] are the butterflies
// printf("[%d, %d] and [%d, %d]\n", i, i + l - 1, i + l, i + l + l - 1);
for(int a = i; a <= i + l - 1; a++)
for(int b = i + l; b <= min(n, i + l + l - 1); b++) {
// printf("%d and %d is %d\n", a, b, cp);
pairing[a][b] = cp;
pairing[b][a] = cp;
}
// we go to a different butterfly
cp++;
}
}
for(int i = 1; i <= n; i++) for(int j = i+1; j <= n; j++) {
expectedSize[pairing[i][j]]++;
}
// printf("%d\n", cp);
}
int hasEdge(int u, int v) {
u++, v++;
if(u > v) swap(u, v);
int retval = 0;
// printf("group %d, curr %d expected %d\n", pairing[u][v], currSize[pairing[u][v]], expectedSize[pairing[u][v]]);
if(currSize[pairing[u][v]] == expectedSize[pairing[u][v]] - 1) {
retval = 1;
}
currSize[pairing[u][v]]++;
return retval;
}
