#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int pred[1510];
int rang[1510];
int step[1510];
int find(int v) {
if (pred[v] == v)return v;
return pred[v] = find(pred[v]);
}
void make(int v, int n) {
pred[v] = v;
rang[v] = 1;
step[v] = n - 1;
return;
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b)return;
if (rang[a] < rang[b])
swap(a, b);
pred[b] = a;
step[a] += step[b];
if (rang[a] == rang[b])
rang[a]++;
}
int was[1510][1510];
void initialize(int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
was[i][j] = -1;
}
}
for (int i = 1; i <= n; i++)
make(i, n);
}
int hasEdge(int u, int v) {
u++; v++;
if (was[u][v] != -1) return was[u][v];
if (u == v) {
was[u][v] = 0;
return 0;
}
if (find(u) == find(v)) {
was[u][v] = 0; was[v][u] = 0;
step[find(u)] -= 2;
return 0;
}
if (step[find(u)] <= 1 || step[find(v)] <= 1) {
was[u][v] = 1; was[v][u] = 1;
merge(u, v);
step[find(u)] -= 2;
return 1;
}
was[u][v] = 0; was[v][u] = 0;
step[find(u)]--;
step[find(v)]--;
return 0;
}
/**
4
0 3
1 0
0 2
3 1
1 2
2 3
4
0 3
2 0
0 1
1 2
1 3
2 3
4
0 1
3 0
1 2
0 2
3 1
2 3
*/
