#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include "game.h" #include <bits/stdc++.h> using namespace std; const int mxn = 1500; int edge[mxn][mxn]; int N; int par[mxn]; vector<int> comp[mxn]; int get(int u){ if(par[u]<0) return u; return par[u] = get(par[u]); } void initialize(int n) { fill(par,par+n,-1); for(int i = 0; i < n; i++) comp[i].push_back(i); N = n; for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) edge[i][j] = 1; } int hasEdge(int u, int v) { int p1 = get(u), p2 = get(v); if(par[p1] > par[p2]) swap(p1,p2); edge[min(p1,p2)][max(p1,p2)]--; if(edge[min(p1,p2)][max(p1,p2)]) return 0; for(int i = 0; i < N; i++) if(i!=p1 && i!=p2 && par[i]<0) edge[min(p1,i)][max(p1,i)] += edge[min(p2,i)][max(p2,i)]; par[p1] += par[p2]; par[p2] = p1; return 1; }