#include <iostream>
#include <vector>
#include "game.h"
using namespace std;
int n;
int const NMAX = 1500;
int root[1 + NMAX];
int treeSize[1 + NMAX];
int unchecked[1 + NMAX][1 + NMAX];
int findRoot(int node) {
if(root[node] == node) {
return node;
}
root[node] = findRoot(root[node]);
return root[node];
}
void combineNode(int a, int b) {
int rootA = findRoot(a), rootB = findRoot(b);
if(rootA != rootB) {
if(treeSize[rootA] < treeSize[rootB]) {
treeSize[rootB] += treeSize[rootA];
root[rootA] = rootB;
for(int i = 1;i <= n;i++) {
unchecked[rootB][i] += unchecked[rootA][i];
unchecked[i][rootB] += unchecked[i][rootA];
unchecked[rootA][i] = unchecked[i][rootA] = 0;
}
}else {
treeSize[rootA] += treeSize[rootB];
root[rootB] = rootA;
for(int i = 1;i <= n;i++) {
unchecked[rootA][i] += unchecked[rootB][i];
unchecked[i][rootA] += unchecked[i][rootB];
unchecked[rootB][i] = unchecked[i][rootB] = 0;
}
}
}
return;
}
void initialize(int m) {
n = m;
for(int i = 1;i <= n;i++) {
root[i] = i;
treeSize[i] = 1;
for(int j = 1;j <= n;j++) {
if(i != j) {
unchecked[i][j] = 1;
}
}
}
return;
}
bool isLastEdge(int a, int b) {
int rootA = findRoot(a), rootB = findRoot(b);
//cerr << rootA << ' ' << rootB << ":\n";
if(rootA != rootB) {
unchecked[rootA][rootB]--;
unchecked[rootB][rootA]--;
//cerr << " " << unchecked[rootA][rootB] << '\n';
if(unchecked[rootA][rootB] == 0) {
return true;
}
}
return false;
}
int hasEdge(int a, int b) {
//cerr << "what the heck!?";
a++;
b++;
if(isLastEdge(a, b)) {
combineNode(a, b);
return 1;
}
return 0;
}
