public static class WeightedQuickUnion {
        private int [] components, sizeComponents;
        private int countComponents;

        public WeightedQuickUnion(int size) {
            components = new int [size];
            sizeComponents = new int [size];
            for (int i = 0; i < size ; i++) {
                components[i] = i;
                sizeComponents[i] = 1;
            }
            countComponents = size;
        }

        public void union(int p, int q) {
            int rootP = root(p);
            int rootQ = root(q);
            if(rootP == rootQ)
                return;
            if(sizeComponents[rootP] < sizeComponents[rootQ]) {
                components[rootP] = rootQ;
                sizeComponents[rootQ] += sizeComponents[rootP];
            }
            else {
                components[rootQ] = rootP;
                sizeComponents[rootP] += sizeComponents[rootQ];
            }
            countComponents--;
        }

        private int root(int p) {
            while (components[p] != p)
                p = components[p];
            return p;
        }

        public boolean sameRoot(int p, int q) {
            return root(p) == root(q);
        }

        public int getSizeComponent(int i) {
            return sizeComponents[root(i)];
        }
    }