class UnionFind:
    def __init__(self, N):
        self.reps = []
        
        for i in range(N):
            self.reps.append(i)

    def find(self, x):
        if self.reps[x] != x:
            self.reps[x] = self.find(self.reps[x])
        return self.reps[x]

    def union(self, v1, v2):
        self.reps[self.find(v1)] = self.find(v2)