class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        # 1. Sort logs by timestamp (index 0) to ensure chronological order
        logs.sort(key=lambda x: x[0])
        
        # Initialize Union-Find structures
        # parent[i] points to the parent of node i
        parent = list(range(n))
        # group_count tracks the number of disjoint sets
        group_count = n
        
        # Helper: Find the representative (root) of group x with Path Compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # Helper: Unite two groups. Returns True if a merge happened.
        def union(x, y):
            root_x = find(x)
            root_y = find(y)
            
            if root_x != root_y:
                # Merge the sets (arbitrarily attach y to x)
                parent[root_y] = root_x
                return True
            return False

        # 2. Iterate through sorted logs
        for timestamp, x, y in logs:
            if union(x, y):
                group_count -= 1
                
                # 3. Check if everyone is in one group
                if group_count == 1:
                    return timestamp
        
        # If we process all logs and still have > 1 group
        return -1