class UnionFind {
 
    constructor(n) {
        this.par = new Map();
        this.rank = new Map();
 
        for (let i = 1; i < n + 1; i++) {
            this.par.set(i,i);
            this.rank.set(i,0);
        }
    }
 
    // Find parent of n, with path compression.
    find(n) {
        let p = this.par.get(n);
        while (p != this.par.get(p)) {
            this.par.set(p, this.par.get(this.par.get(p)));
            p = this.par.get(p);
        }
        return p;
    }
 
    // Union by height / rank.
    // Return false if already connected, true otherwise.
    union(n1, n2) {
        let p1 = this.find(n1), p2 = this.find(n2);
        if (p1 == p2) {
            return false;
        }
 
        if (this.rank.get(p1) > this.rank.get(p2)) {
            this.par.set(p2, p1);
        } else if (this.rank.get(p1) < this.rank.get(p2)) {
            this.par.set(p1, p2);
        } else {
            this.par.set(p1, p2);
            this.rank.set(p2, this.rank.get(p2) + 1);
        }
        return true;
    }
}