public class UF {
    private int[] pai;
    private int[] sz;
    private int count;

    // Initializes an empty union-find data structure with n
    // isolated components 0 through n-1
    public UF(int n) {
        count = n;
        pai = new int[n];
        sz = new int[n];
        for (int i = 0; i < n; i++) {
            pai[i] = i;
            sz[i] = 1;
        }
    }

    // Return the number of components.
    public int count() {
        return count;
    }

    // Are the two sites p and q in the same component?
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    // Return the component identifier for the component
    // containing site p.
    public int find(int p) {
        while (p != pai[p]) {
            pai[p] = pai[pai[p]];  // diminui o tamanho do caminho a metade
            p = pai[p];
        }
        return p;
    }

    // Merge the component containing site p with the the
    // component containing site q.
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return ;

        if (sz[pRoot] < sz[qRoot]) {
            pai[pRoot] = pai[qRoot];
            sz[qRoot] += sz[pRoot];
        }
        else {    
            pai[qRoot] = pai[pRoot];
            sz[pRoot] += sz[qRoot];
        }
        count--;
    }
        
}