#include <bits/stdc++.h>
#include "game.h"
using namespace std;
vector<set<int> > grafo;
vector<map<int, int> > Marc;
vector<int> pai;
vector<int> prof;
int quantF = 2;
int N;
int find(int v)
{
if (v == pai[v]) return v;
return pai[v] = find(pai[v]);
}
void une(int a, int b)
{
a = find(a); b = find(b);
if (a == b) return;
if (prof[a] < prof[b]) swap(a, b);
pai[b] = a;
prof[a] = max(prof[a], prof[b] + 1);
for (int j = 0; j < N; j++) Marc[a][j] += Marc[b][j];
for (auto x : grafo[b]) grafo[a].insert(find(x));
}
void initialize(int n) {
grafo.resize(n+1);
pai.resize(n+1);
prof.resize(n+1);
Marc.resize(n+1);
N = n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) if (i != j) {grafo[i].insert(j); Marc[i][j] = 1;}
pai[i] = i;
prof[i] = 1;
}
}
int hasEdge(int u, int v)
{
u = find(u); v = find(v);
if (u == v) return 0;
// cerr << "PENIS" << '\n';
for (auto x = grafo[u].begin(); x != grafo[u].end();)
{
if (find(*x) != *x || *x == u) x = grafo[u].erase(x);
else x++;
}
for (auto x = grafo[v].begin(); x != grafo[v].end();)
{
if (find(*x) != *x || *x == v) x = grafo[v].erase(x);
else x++;
}
/*
cerr << u << " " << v << '\n';
cerr << Marc[u][v] << " " << Marc[v][u] << '\n';
cerr << grafo[u].size() << " " << grafo[v].size() << '\n';
*/
if (Marc[u][v] == 0 && Marc[v][u] == 0)
{
Marc[u][v] = Marc[v][u] = 0;
grafo[u].erase(v); grafo[v].erase(u);
return 0;
}
else if (Marc[u][v] > 1 && Marc[v][u] > 1)
{
Marc[u][v]--;
Marc[v][u]--;
return 0;
}
else if (grafo[u].size() > 2 && grafo[v].size() > 2)
{
Marc[u][v]--;
Marc[v][u]--;
if (Marc[u][v] == 0) grafo[u].erase(v);
if (Marc[v][u] == 0) grafo[v].erase(u);
return 0;
}
else if (grafo[u].size() == 2 && grafo[v].size() == 2)
{
if (quantF == 2)
{
Marc[u][v]--;
Marc[v][u]--;
if (Marc[u][v] == 0) {grafo[u].erase(v);}
if (Marc[v][u] == 0) {grafo[v].erase(u);}
if (grafo[u].size() == 1) quantF--;
if (grafo[v].size() == 1) quantF--;
return 0;
}
else
{
Marc[u][v] = Marc[v][u] = 0;
grafo[u].erase(v); grafo[v].erase(u);
une(u, v);
return 1;
}
}
else if ((grafo[u].size() == 2 || grafo[v].size() == 2))
{
if (quantF)
{
Marc[u][v]--;
Marc[v][u]--;
if (Marc[u][v] == 0) {grafo[u].erase(v);}
if (Marc[v][u] == 0) {grafo[v].erase(u);}
if (grafo[u].size() == 1) quantF--;
if (grafo[v].size() == 1) quantF--;
return 0;
}
else
{
Marc[u][v] = Marc[v][u] = 0;
grafo[u].erase(v); grafo[v].erase(u);
une(u, v);
return 1;
}
}
else if (grafo[u].size() == 1 || grafo[v].size() == 1)
{
Marc[u][v] = Marc[v][u] = 0;
grafo[u].erase(v); grafo[v].erase(u);
une(u, v);
return 1;
}
else
{
Marc[u][v]--;
Marc[v][u]--;
if (Marc[u][v] == 0) grafo[u].erase(v);
if (Marc[v][u] == 0) grafo[v].erase(u);
return 0;
}
}
