#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "game.h"
struct DSU {
vi e;
void init(int N) {
e = vi(N, -1);
}
int root(int x) {
if (e[x] < 0) {
return x;
}
else {
e[x] = root(e[x]);
return e[x];
}
}
bool sameset(int x, int y) {
return(root(x) == root(y));
}
bool merge(int x, int y) {
x = root(x);
y = root(y);
if (x == y)
return false;
if (-e[x] < -e[y])
swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
int size(int x) {
return -e[root(x)];
}
};
const int MAX = 1505;
int N;
DSU dsu;
int ccs;
bool flag1 = false; // already have three comps
vi roots;
vi cnts(3, 0); // count of 01, 02, 12
vi szs(3, 0);
map<int, int> conv;
int ctr = 0; // how many pairs of comps fully filled
// first pair fully filled is 1, second is 0, last is 1
void initialize(int n) {
N = n;
dsu.init(N);
ccs = N;
}
int hasEdge(int u, int v) {
if (!flag1) {
if (!dsu.sameset(u, v))
ccs--;
dsu.merge(u, v);
if (ccs == 3) {
flag1 = true;
// go into pairing mode
set<int> setr; // set of roots
for (int i = 0; i < N; i++) {
setr.insert(dsu.root(i));
}
for (int x : setr)
roots.pb(x);
for (int i = 0; i < 3; i++) {
szs[i] = dsu.size(roots[i]);
conv[roots[i]] = i;
}
/* cout<<"roots: ";
for (int x : roots)
cout<<x<<" ";
cout<<endl;
cout<<"szs: ";
for (int x : szs)
cout<<x<<" ";
cout<<endl;*/
}
return 1;
}
else {
u = dsu.root(u);
v = dsu.root(v);
if (u == v)
return 1;
int r1 = conv[u];
int r2 = conv[v];
int pos = r1 + r2 - 1;
// cout<<"r1, r2, pos: "<<r1<<" "<<r2<<" "<<pos<<endl;
cnts[pos]++;
// cout<<"cnts["<<pos<<"]: "<<cnts[pos]<<endl;
if (cnts[pos] == szs[r1] * szs[r2]) {
// cout<<"orz"<<endl;
ctr++;
if (ctr == 1 || ctr == 3)
return 1;
else
return 0;
}
else {
return 0;
}
}
}
