// In the name of Allah
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1500 + 4;
int n; int M[maxn][maxn];
bool mark[maxn]; int sz;
void initialize(int Nx) {
n = Nx;
mark[0] = 1; sz = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) M[i][j] = -1;
}
}
int hasEdge(int u, int v) {
if (M[u][v] != -1) return M[u][v];
if (!mark[u] && !mark[v]) {
M[u][v] = M[v][u] = 0;
return M[u][v];
}
else if (mark[u] && mark[v]) {
M[u][v] = M[v][u] = 0;
return M[u][v];
}
int t = 0;
if (!mark[u]) swap(u, v);
for (int i = 0; i < n; i++) {
if (!mark[i]) continue;
if (M[i][v] != -1) t++;
}
if (t == sz - 1) {
M[u][v] = M[v][u] = 1;
mark[v] = 1; sz++;
}
else {
M[u][v] = M[v][u] = 0;
}
return M[u][v];
}
