class UnionFind:

    # Constructor
    def __init__(self, n):
        self.parent = []
        for i in range(n + 1):
            self.parent.append(i)

    # Function to find which subset a particular element belongs to
    def find_parent(self, v):
        if self.parent[v] != v:
            return self.find_parent(self.parent[v])
   
    # Function to join two subsets into a single subset
    def union(self, v1, v2):
        p1, p2 = self.find_parent(v1), self.find_parent(v2)
        self.parent[p1] = p2