#include<vector>
struct Unionfind {
vector<int> par, rank, size;
Unionfind(int n) : par(n), rank(n), size(n){
for(int i=0;i<n;i++){
par[i] = i;
rank[i] = 0;
size[i] = 1;
}
}
int find(int x){
if(par[x] == x){
return x;
}
return par[x] = find(par[x]);
}
void unite(int x, int y){
x = find(x);
y = find(y);
if(x == y) return;
if(rank[x] < rank[y]){
par[x] = par[y];
size[y] += size[x];
}else{
par[y] = par[x];
size[x] += size[y];
if(par[x] == par[y]) rank[x]++;
}
}
int get_size(int x) {
return size[find(x)];
}
bool same(int x, int y){
return find(x) == find(y);
}
};