class Disjoint{
vector<int> parent, rank, size;
public:
Disjoint(int n){
rank.resize(n+1,0);
parent.resize(n+1);
size.resize(n+1,1);
for(int i=0; i<=n; i++)
parent[i] = i;
}
int find_ultimate_parent(int node){
if(node == parent[node])
return node;
return parent[node] = find_ultimate_parent(parent[node]);
}
void union_by_rank(int u, int v){
int ul_u = find_ultimate_parent(u);
int ul_v = find_ultimate_parent(v);
if(ul_u == ul_v)
return ;
else if(rank[ul_u] > rank[ul_v]){
parent[ul_v] = ul_u;
}
else if(rank[ul_v] > rank[ul_u]){
parent[ul_u] = ul_v;
}
else{
parent[ul_v] = ul_u;
rank[ul_u]++;
}
}
void union_by_size(int u, int v){
int ul_u = find_ultimate_parent(u);
int ul_v = find_ultimate_parent(v);
if(ul_u == ul_v)
return ;
else if(size[ul_u] > size[ul_v]){
parent[ul_v] = ul_u;
size[ul_u] += size[ul_v];
}
else{
parent[ul_u] = ul_v;
size[ul_v] += size[ul_u];
}
}
};