#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
vector<int>rt,siz;
int N;
map<int,int>queried[1501];
int root(int x){
while (x!=rt[x]){
rt[x]=rt[rt[x]];
x=rt[x];
}
return x;
}
void merge(int a, int b){
if (siz[a]<siz[b])
swap(a,b);
for (auto it:queried[b]){
queried[a][it.first]+=it.second;
queried[it.first][a]+=queried[it.first][b];
//queried[it.first].erase(b);
queried[it.first][b]=0;
}
queried[b].clear();
siz[a]+=siz[b];
rt[b]=a;
}
void initialize(int N){
for (int i=0;i<N;i++)
rt.push_back(i);
for (int i=0;i<N;i++)
siz.push_back(1);
}
int hasEdge(int U, int V){
U=root(U);
V=root(V);
if (U==V)
return 0;
queried[U][V]++;
queried[V][U]++;
if (queried[U][V]==siz[U]*siz[V]){
merge(U,V);
return 1;
}
else
return 0;
}
