class UnionFind:
    def __init__(self, n: int):
        # parent[i] = parent of i (if parent[i] == i, i is a root)
        self.parent = list(range(n))
        # size[i] = size of the set whose root is i (only valid for roots)
        self.size = [1] * n

    def find(self, x: int) -> int:
        # Find root with path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        # Union sets containing a and b
        ra = self.find(a)
        rb = self.find(b)

        if ra == rb:
            return False  # already in same set

        # Union by size (attach smaller under larger)
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra

        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

    def same(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def component_size(self, x: int) -> int:
        return self.size[self.find(x)]