#include<iostream> 
#include<vector>
using namespace std;

class DSU{
private:
    vector<int> parent;
    vector<int> rank;
public:
    DSU(int n){
        parent.resize(n+1);
        rank.resize(n+1,1);
        for(int i = 1; i <= n; i++) parent[i] = i;
    }
    
    int find(int a){
        if(parent[a] != a) parent[a] = find(parent[a]);
        return parent[a];
    }
    
    void unite(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx == rooty) return;
        if(rank[rootx] > rank...