#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#define dbg(...) 199958
#endif
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
template<class T,auto op,int extra>
struct base_dsu{
vector<int>par;
vector<T>data;
base_dsu(int n):par(n,-1){
static_assert(!extra,"e is needed");
}
base_dsu(int n,T e):par(n,-1),data(n,e){}
T& operator[](int i){
static_assert(extra,"No data");
return data[leader(i)];
}
int root(int x){
if(par[x]<0)return x;
else return par[x]=root(par[x]);
}
bool same(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;
par[x]+=par[y];
par[y]=x;
return true;
}
int size(int x){
return -par[root(x)];
}
int leader(int x){
return root(x);
}
};
int tf323(int a,int b){return a;}
using dsu=base_dsu<int,tf323,0>;
template<class T,auto op>
using extra_dsu=base_dsu<T,op,1>;
constexpr int N=1500;
dsu ds(N);
int cnt[N][N];
unordered_map<int,int>edge[N];
void initialize(int n) {
ds=dsu(N);
rep(i,N)rep(j,N)cnt[i][j]=0;
rep(i,N)edge[i].clear();
}
int hasEdge(int u, int v) {
u=ds.root(u),v=ds.root(v);
assert(u!=v);
if(cnt[u][v]==ds.size(u)*ds.size(v)-1){
if(edge[u].size()<edge[v].size())swap(u,v);
for(auto&[x,cn]:edge[v]){
if(ds.same(x,v)||ds.same(x,u))continue;
assert(x==ds.root(x));
edge[u][x]+=cn;
cnt[u][x]+=cn;
cnt[x][u]+=cn;
edge[x][v]-=cn;
edge[x][u]+=cn;
}
ds.merge(u,v);
return 1;
}else{
edge[u][v]++;
edge[v][u]++;
cnt[u][v]++,cnt[v][u]++;
return 0;
}
}
mt19937 mt(2);
namespace judge{
void run(){
while(1){
int n=5;
initialize(n);
vc<pair<int,int>>edge;
rep(i,n)REP(j,i+1,n)edge.push_back({i,j});
shuffle(all(edge),mt);
dbg(edge);
for(auto&[x,y]:edge)dbg(x,y),dbg(hasEdge(x,y));
}
}
};
//int main(){judge::run();}
