#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
int p[1505];
set<pair<int, int>> adj[1505];
int edge[1505][1505];
int find(int x){
return (p[x] == x) ? x : (p[x] = find(p[x]));
}
void onion(int a, int b){
a = find(a), b = find(b);
if(a == b) return;
if(adj[a].size() < adj[b].size()) swap(a, b);
for(auto i : adj[b]){
adj[a].insert(i);
int x = find(i.first), y = find(i.second);
if(y == b) swap(x, y);
edge[min(a, y)][max(a, y)]++;
edge[min(b, y)][max(b, y)]--;
// cout << " WE ONLY MERGED EDGE " << i.first << " TO " << i.second << ", ERASED FROM " << b << ", " << y << " AND ADDED TO " << a << ", " << y << endl;
}
adj[b].clear();
p[a] = p[b] = a;
}
void initialize(int n) {
FOR(i, 0, n - 1) p[i] = i;
FOR(i, 0, n - 1){
FOR(j, i + 1, n - 1){
adj[i].insert(make_pair(i, j));
adj[j].insert(make_pair(i, j));
edge[i][j] = 1;
}
}
}
int hasEdge(int u, int v) {
pair<int, int> e = make_pair(min(u, v), max(u, v));
u = find(u), v = find(v);
if(u == v) return 1;
adj[u].erase(e);
adj[v].erase(e);
edge[min(u, v)][max(u, v)]--;
if(edge[min(u, v)][max(u, v)] == 0){
onion(u, v);
return 1;
}
return 0;
}
/*int main(){
int x; cin >> x;
initialize(x);
FOR(i, 1, (x * (x - 1)) / 2){
int a, b;
cin >> a >> b;
bool res = hasEdge(a, b);
if(res){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
FOR(j, 0, x - 1){
FOR(k, j + 1, x - 1){
cout << "ADJ MATRIX FOR " << j << " TO " << k << " HAS EDGES " << endl;
for(auto i : edge[j][k]){
cout << i.first << " " << i.second << endl;
}
}
}
}
}*/
