vector<int> parent, rnk;
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (rnk[px] < rnk[py]) swap(px, py);
    parent[py] = px;
    if (rnk[px] == rnk[py]) rnk[px]++;
}
 
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    int n = accounts.size();
    parent.resize(n); rnk.resize(n, 0);
    iota(parent.begin(), parent.end(), 0);
 
    unordered_map<string, int> emailToId;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < accounts[i].size(); j++) {
            const string& email = accounts[i][j];
            if (emailToId.count(email)) unite(i, emailToId[email]);
            else emailToId[email] = i;
        }
    }
 
    unordered_map<int, set<string>> groups;
    for (auto& [email, id] : emailToId)
        groups[find(id)].insert(email);
 
    vector<vector<string>> result;
    for (auto& [root, emails] : groups) {
        vector<string> acc = {accounts[root][0]};
        acc.insert(acc.end(), emails.begin(), emails.end());
        result.push_back(acc);
    }
    return result;
}

from collections import defaultdict
 
def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
    n = len(accounts)
    parent = list(range(n))
    rank = [0] * n
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    def unite(x, y):
        px, py = find(x), find(y)
        if px == py:
            return
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
 
    # Map each email to the first account that contains it
    email_to_id = {}
    for i, account in enumerate(accounts):
        for email in account[1:]:
            if email in email_to_id:
                unite(i, email_to_id[email])
            else:
                email_to_id[email] = i
 
    # Group all emails by their root account
    groups = defaultdict(set)
    for email, i in email_to_id.items():
        groups[find(i)].add(email)
 
    return [
        [accounts[root][0]] + sorted(emails)
        for root, emails in groups.items()
    ]

int[] parent, rank;
int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}
void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
    parent[py] = px;
    if (rank[px] == rank[py]) rank[px]++;
}
 
public List<List<String>> accountsMerge(List<List<String>> accounts) {
    int n = accounts.size();
    parent = new int[n]; rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
 
    Map<String, Integer> emailToId = new HashMap<>();
    for (int i = 0; i < n; i++)
        for (int j = 1; j < accounts.get(i).size(); j++) {
            String email = accounts.get(i).get(j);
            if (emailToId.containsKey(email)) unite(i, emailToId.get(email));
            else emailToId.put(email, i);
        }
 
    Map<Integer, TreeSet<String>> groups = new HashMap<>();
    for (Map.Entry<String, Integer> entry : emailToId.entrySet())
        groups.computeIfAbsent(find(entry.getValue()), k -> new TreeSet<>()).add(entry.getKey());
 
    List<List<String>> result = new ArrayList<>();
    for (Map.Entry<Integer, TreeSet<String>> entry : groups.entrySet()) {
        List<String> acc = new ArrayList<>();
        acc.add(accounts.get(entry.getKey()).get(0));
        acc.addAll(entry.getValue());
        result.add(acc);
    }
    return result;
}