DSU

//dsu template
struct DSU{
    int dsu[maxn],size[maxn];
    DSU (int n){
        REP1(i,n){
            dsu[i] = i;
            size[i] = 1;
        }
    }
    inline void reset(int n){
        REP1(i,n){
            dsu[i] = i;
            size[i] = 1;
        }
    }
    inline int query(int k){
        return dsu[k] == k ? k : dsu[k] = query(dsu[k]);
    }
    inline void merge(int u,int v){
        u = query(u); v = query(v);
        if (size[v] > size[u])
            swap(u,v);
        dsu[v] = u;
        size[u] += size[v];
    }
};