# サイズNの森をベースとした互いに素な集合
class DisjointSet:
    parent  # 森を構成する各ノードの親を保持する配列
    rank    # rankを管理する配列

    init(): # 初期化
        for i ← 0 to N-1:
            parent[i] ← i
            rank[i] ← 0

    unite(x, y):
        root1 ← findSet(x)
        root2 ← findSet(y)
        link(root1, root2)

    findSet(x):
        if paret[x] ≠ x:
            parent[x] ← findSet(parent[x])
        return parent[x];

    link(x, y):
        if rank[x] > rank[y]:
            parent[y] ← x
        else:
            parent[x] ← y
            if rank[x] = rank[y]:
                rank[y]++