#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)1504;
int way[NS][NS];
int NN;
struct dsu{
vector < int > pr, rk;
int N;
dsu(){}
dsu(int n):N(n){
pr.resize(N), rk.resize(N);
for(int i = 0; i < N; ++i) pr[i] = i, rk[i] = 1;
}
inline int get(int x){
return x == pr[x] ? x : pr[x] = get(pr[x]);
}
inline bool unite(int x, int y){
x = get(x), y = get(y);
if(x != y){
if(rk[x] < rk[y]) swap(x, y);
for(int i = 0; i < NN; ++i){
way[x][i] += way[y][i];
way[i][x] += way[i][y];
}
pr[y] = x, rk[x] += rk[y];
return true;
}
return false;
}
}group(NS);
int chk[NS][NS];
void initialize(int n) {
NN = n;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
way[i][j] = 1;
}
}
}
int hasEdge(int u, int v) {
if(u > v){
swap(u, v);
}
int a = group.get(u), b = group.get(v);
if(a == b){
return chk[u][v];
}
if(way[a][b] >= 2){
--way[a][b], --way[b][a];
return 0;
}
else{
chk[u][v] = 1;
group.unite(a, b);
return 1;
}
}
