#include "game.h"
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> w, p;
vector<vector<int>> am;
int find(int a){
if (p[a] == a) return a;
return p[a] = find(p[a]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if (a == b) return;
p[a] = b;
}
void initialize(int n){
N = n;
w.resize(N, N-1);
p.resize(N);
for (int i=0; i<N; i++) p[i] = i;
am.resize(N, vector<int>(N, 1));
for (int i=0; i<N; i++) am[i][i] = 0;
am[0][1] = 0;
am[1][0] = 0;
w[0]--;
w[1]--;
}
void connect(int t, int u, int v){
if (t == 0){
am[u][v] = 0;
am[v][u] = 0;
w[u]--;
w[v]--;
if (w[u] == 1 || (w[u] == 2 && u >= 2)){
for (int i=0; i<N; i++){
if (am[u][i] == 1) connect(1, u, i);
}
}
if (w[v] == 1 || (w[v] == 2 && v >= 2)){
for (int i=0; i<N; i++){
if (am[v][i] == 1) connect(1, v, i);
}
}
return;
}
am[u][v] = 2;
am[v][u] = 2;
if (find(u) == find(0)){
for (int i=0; i<N; i++){
if (find(i) == find(v)){
for (int j=0; j<N; j++){
if (find(j) == find(1)) connect(0, i, j);
}
}
}
}
if (find(u) == find(1)){
for (int i=0; i<N; i++){
if (find(i) == find(v)){
for (int j=0; j<N; j++){
if (find(j) == find(0)) connect(0, i, j);
}
}
}
}
if (find(v) == find(0)){
for (int i=0; i<N; i++){
if (find(i) == find(u)){
for (int j=0; j<N; j++){
if (find(j) == find(1)) connect(0, i, j);
}
}
}
}
if (find(v) == find(1)){
for (int i=0; i<N; i++){
if (find(i) == find(u)){
for (int j=0; j<N; j++){
if (find(j) == find(0)) connect(0, i, j);
}
}
}
}
merge(u, v);
}
int hasEdge(int u, int v){
if (am[u][v] == 2) return 1;
connect(0, u, v);
return 0;
}
