type UnionFind struct {
    parent []int // 父节点
    rank   []int // 秩（树的高度）
}

func (uf *UnionFind) Find(x int) int {
    if x != uf.parent[x] {
       // 递归查找并将父节点直接指向根（路径压缩）
       uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)

    if rootX == rootY {
       return
    }

    // 将秩小的树合并到秩大的树下（按秩合并）
    if uf.rank[rootX] > uf.rank[rootY] {
       uf.parent[rootY] = rootX
    } else if uf.rank[rootX] < uf.rank[rootY] {
       uf.parent[rootX] = rootY
    } else {
       // 秩相等时，任意合并，并增加新根的秩
       uf.parent[rootY] = rootX
       uf.rank[rootX]++
    }
}

uf := &UnionFind{parent: make([]int, n), rank: make([]int, n)}
// 初始时，每个元素的父节点指向自己
for i := 0; i < n; i++ {
    uf.parent[i] = i
}