class UnionFind:
    def __init__(self, idx: int):
        self.idx = idx
        self.parent = self
        self.height = 1

    def find(self) -> "UnionFind":
        if self.parent is self:
            return self

        self.parent = self.parent.find()
        return self.parent

    def union(self, other: "UnionFind") -> None:
        sp = self.find()
        lp = other.find()
        if sp is lp:
            return

        if sp.height > lp.height:
            sp, lp = lp, sp

        sp.parent = lp
        if sp.height == lp.height:
            lp.height += 1

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        N = len(accounts)
        ufs = [UnionFind(i) for i in range(N)]

        email_ufs = {}

        for i, account in enumerate(accounts):
            uf = ufs[i]
            for email in itertools.islice(account, 1, None):
                if email in email_ufs:
                    email_ufs[email].union(uf)
                else:
                    email_ufs[email] = uf

        ans = {}
        for uf in ufs:
            i = uf.idx
            pi = uf.find().idx
            if pi not in ans:
                ans[pi] = set()
            ans[pi].update(itertools.islice(accounts[i], 1, None))

        return [
            [accounts[pi][0]] + sorted(emails) for pi, emails in ans.items()
        ]