class Partition:
    def __init__(P,n):
      # sometimes called makeset(j)
      P.parent = [j for j in range(n)]
      P.weight = [1] * n

    def find(P, key):
      if P.parent[key] != key:
          key = P.find(P.parent[key])
      return key

    def union(P,x,y):
      rx = P.find(x)
      ry = P.find(y)

      if rx == ry:
          return

      if P.weight[rx] > P.weight[ry]:
          P.parent[ry] = rx
          P.weight[rx] += P.weight[ry]
      else:
          P.parent[rx] = ry
          P.weight[ry] += P.weight[rx]