#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1505;
int n;
int deg[mxn];
bool resp[mxn][mxn];
bool adj[mxn][mxn];
void initialize(int N) {
n = N;
for(int i = 0; i < n; i++) deg[i] = n-1;
}
int hasEdge(int u, int v) {
if(adj[u][v]) return true;
queue<int> q;
deg[u]--; if(deg[u] == 1) q.push(u);
deg[v]--; if(deg[v] == 1) q.push(v);
resp[u][v] = resp[v][u] = true;
while(!q.empty()) {
int i = q.front(); q.pop();
for(int j = 0; j < n; j++) if(i != j && !resp[i][j] && !adj[i][j]) {
adj[i][j] = adj[j][i] = true;
deg[j]--; if(deg[j] == 1) q.push(j);
}
}
// cerr << "degs:\n";
// for(int i = 0; i < n; i++) {
// cerr << deg[i] << " ";
// }
// cerr << "adj:\n";
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < n; j++) {
// cerr << adj[i][j];
// }
// cerr << "\n";
// }
return adj[u][v];
}
