def dfs_pre(r, c, grid):
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] == '0':
        return

    grid[r][c] = '0'  # mark visited (pre-order processing)

    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
        dfs_pre(r + dr, c + dc, grid)

# Example: numIslands uses pre-order DFS to flood fill

def inorder(node, res):
    if not node:
        return
    inorder(node.left, res)
    res.append(node.val)  # process node in between left/right
    inorder(node.right, res)

# Example: LeetCode 98, Validate BST or BST inorder traversal

def dfs_post(r, c, grid):
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] == '0':
        return 0

    grid[r][c] = '0'  # mark visited
    size = 1  # count current cell

    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
        size += dfs_post(r + dr, c + dc, grid)

    return size  # post-order: aggregate after children

# Example: maxAreaOfIsland uses post-order DFS to sum area

def bfs_shortest(grid, start):
    queue = deque([(*start, 0)])  # (r, c, distance)
    visited = set([start])

    while queue:
        r, c, dist = queue.popleft()
        if grid[r][c] == 'target':
            return dist

        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (nr,nc) not in visited:
                visited.add((nr,nc))
                queue.append((nr,nc, dist + 1))

    def numIslandsUnion(grid):
        parent = {}
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            parent[find(x)] = find(y)
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == '1':
                    parent[(r,c)] = (r,c)
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == '1':
                    for dr, dc in [(1,0),(0,1)]:
                        nr, nc = r+dr, c+dc
                        if (nr,nc) in parent:
                            union((r,c),(nr,nc))
        
        roots = {find(x) for x in parent}
        return len(roots)

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        
        # Note:
        # Counting the number of connected components 
        # using a Adjacency Matrix

        # Adjacency Matrix:

        #            0  1  2  3
        # matrix = [
        #           [0, 1, 1, 0],     0
        #           [1, 0, 1, 0],     1
        #           [1, 1, 0, 1],     2
        #           [0, 0, 1, 0],     3
        # ]

        # By representing the cities as nodes in a connected graph,
        # we can use DFS to explore all connected cities starting from any city
        # in the province.
        # Provinces then become a representation of connected components,
        # so we are counting the number of connected components in the graph.
         
        n = len(isConnected)

        # Tracking visited cities to avoid revisiting
        # and to check if we have found a new province/connected component
        visited = set()

        # Number of connected components
        provinces = 0

        # For current province connect all cities,
        # meaning explore all cities and their connections
        def dfs(city):

            # Early Pruning:
            if city in visited:
                return

            # Process root
            visited.add(city)

            # Explore neighbors
            for nei in range(n):
                if isConnected[city][nei] == 1:
                    dfs(nei)

        # Run DFS for each province,
        # which will mark all connected cities by adding them to visited set
        for city in range(n):

            # New province has been found
            if city not in visited:
                provinces += 1
                dfs(city)

        # overall: tc O(n^2)
        # overall: sc O(n)
        return provinces

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        
        # Note:
        # Counting the number of connected components 
        # using a Adjacency Matrix

        # Adjacency Matrix:

        #            0  1  2  3
        # matrix = [
        #           [0, 1, 1, 0],     0
        #           [1, 0, 1, 0],     1
        #           [1, 1, 0, 1],     2
        #           [0, 0, 1, 0],     3
        # ]

        # By representing the cities as nodes in a connected graph,
        # we can use BFS to explore all connected cities starting from any city
        # in the province.
        # Provinces then become a representation of connected components,
        # so we are counting the number of connected components in the graph.

        n = len(isConnected)
        visited = set()
        provinces = 0

        def bfs(start):

            queue = deque([start])
            visited.add(start)

            while queue:

                # Run BFS for each province,
                # which will mark all connected cities by adding them to visited set
                city = queue.popleft()

                # Explore neighbors
                for nei in range(n):
                    if (isConnected[city][nei] == 1 and
                        nei not in visited):

                        # Mark as visited and enqueue for further exploration
                        visited.add(nei)
                        queue.append(nei)

        # Run BFS for each province,
        # which will mark all connected cities by adding them to visited set        
        for city in range(n):

            # New province has been found
            if city not in visited:
                provinces += 1
                bfs(city)

        # overall: tc O(n^2)
        # overall: sc O(n)
        return provinces

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        
        # Note:
        # Counting the number of connected components 
        # using a Adjacency Matrix

        # Adjacency Matrix:

        #            0  1  2  3
        # matrix = [
        #           [0, 1, 1, 0],     0
        #           [1, 0, 1, 0],     1
        #           [1, 1, 0, 1],     2
        #           [0, 0, 1, 0],     3
        # ]

        # By representing the cities as nodes in a connected graph,
        # we can use DFS to explore all connected cities starting from any city
        # in the province.
        # Provinces then become a representation of connected components,
        # so we are counting the number of connected components in the graph.

        n = len(isConnected)

        # Union Find Data Structure:
        # sc: O(n)
        parent = list(range(n))
        rank = [0] * n

        # Find():
        # with path compression
        def find(x):

            if parent[x] != x:
                # Path Compression:
                parent[x] = find(parent[x])

            return parent[x]

        # Union():
        # adding by rank
        def union(x, y):

            rootX, rootY = find(x), find(y)

            # Early pruning:
            if rootX == rootY:
                return

            # Smaller rank tree becomes a subtree of the larger rank tree
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX

                # On a tie, add to rank to mark X the higher rank tree
                rank[rootX] += 1

        # Only check upper triangle (optimization)
        # by only looking at a cell if its column number is bigger than its row number
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)

        # Count the number of unique roots, 
        # which corresponds to the number of provinces
        roots = set()
        for city in range(n):
            roots.add(find(city))

        # overall: tc O(n^2 * α(n))
        # overall: sc O(n)
        return len(roots)

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        
        # Note:
        # Counting the number of connected components 
        # using an Edge List

        # Edge List:
        # edges = [
        #     [0, 1],
        #     [0, 2],
        #     [1, 2],
        #     [2, 3],
        # ]

        # Adjacency List:
        # graph = {
        #           0: [1, 2],
        #           1: [0, 2],
        #           2: [0, 1, 3],
        #           3: [2],
        #         }

        # Connected Components In A Graph:
        # Each node represents a vertex.
        # Each edge connects two nodes bidirectionally.
        # The problem asks for the number of connected components.

        # DFS Approach:
        # 1. Build adjacency list (graph representation).
        # 2. Start DFS from every unvisited node.
        # 3. DFS marks all nodes belonging to that component.
        # 4. Each new DFS call = new connected component.
        

        # Build adjacency list
        # tc: O(E), sc: O(V + E)
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Track visited nodes
        # sc: O(V)
        visited = set()
        
        # Recursive DFS traversal
        # sc: O(V) recursion stack worst case
        def dfs(node):

            # Explore:
            # visit all neighbors
            # tc: O(deg(node))
            for nei in graph[node]:

                # Early Pruning:
                # skip already visited nodes
                if nei not in visited:

                    # Process Root:
                    # mark neighbor as visited
                    # tc: O(!)
                    visited.add(nei)

                    # Explore:
                    # recursively explore neighbor
                    dfs(nei)
        
        # Count connected components
        # tc: O(V)
        components = 0

        # Iterate over all nodes
        # tc: O(V)
        for i in range(n):

            # Initial Call:
            # new component found
            if i not in visited:

                # mark root as visited
                visited.add(i)

                # recursively explore
                dfs(i)

                # add to component counter
                components += 1

        # overall: tc O(V + E)
        # overall: sc O(V + E)
        return components

    def countComponents(self, n: int, edges: List[List[int]]) -> int:

        # Connected Components In A Graph:
        # BFS explores nodes level-by-level using a queue.
        # Each BFS traversal fully visits one connected component.

        # Build adjacency list
        # tc: O(E), sc: O(V + E)
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # visited tracking
        # sc: O(V)
        visited = set()
        
        # BFS traversal
        # sc: O(V) queue worst-case
        def bfs(start):

            # Iterative Queue:
            # sc: O(V)
            queue = deque()

            # Process Root:
            # add to queue to process
            # tc: O(V)
            queue.append(start)

            # While we still have nodes connected to root node
            while queue:

                # Grab original node
                node = queue.popleft()

                # Explore:
                # recursively explore neighbors
                # tc: O(V)
                for nei in graph[node]:

                    # Early Prune:
                    # if neighbor has not been explore
                    # tc: O(1)
                    if nei not in visited:

                        # Process root:
                        # mark as visited
                        # tc: O(1)
                        visited.add(nei)

                        # Append to queue to process
                        # tc: O(1)
                        queue.append(nei)
        
        # Global component counter
        components = 0

        # Iterate over all nodes
        # tc: O(n)
        for i in range(n):

            # Early Prune:
            # only process if node has not been visited
            # tc: O(1)
            if i not in visited:

                # Process Root:
                # mark as visited
                visited.add(i)

                # Explore:
                # recursively explore neighbors
                # tc: O(V)
                bfs(i)

                # Add to global component
                components += 1

        # overall: tc O(V + E)
        # overall: sc O(V + E)
        return components

    def countComponents(self, n: int, edges: List[List[int]]) -> int:

        # Note:
        # Counting the number of connected components 
        # using an Edge List

        # Unlike DFS and BFS for an Edge List, 
        # Union Find does not require to create a new data structure to traverse,
        # as it can operate directly on the Edge List.

        # Edge List Graph Representation:
        # Each node represents a vertex (0 to n-1)
        # Each edge connects two nodes bidirectionally
        # The problem asks for the number of connected components


        # Parent and Rank Initialization:
        # Each node starts as its own parent
        # Rank is used to keep the trees shallow
        parent = {}
        rank = {}

        # Initialize each node
        # tc: O(n), sc: O(n)
        for i in range(n):
            parent[i] = i    # initially, parent of node i is itself
            rank[i] = 0      # initial rank (upper bound on tree height)
        
        # Find with Path Compression
        # Returns the root of a node's tree
        # tc: O(α(n)) 
        def find(x):
            # parent is not self, recurse upwards
            if parent[x] != x:
                # recursively find root and compress path
                parent[x] = find(parent[x])

            # return original call's parent, after path compression
            return parent[x]
        
        # Union by Rank
        # Connect two nodes together if they are not already connected
        # tc: O(α(n))
        def union(x, y):

            # If they share the same root, they are already in the same component
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return 0
            
            
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1
            return 1  # successful merge
        
        # Assume all nodes are components
        # sc: O(1)
        components = n

        # Iterate over all edges
        # tc: O(E * α(n))
        for u, v in edges:

            # Every successful Union implies that we have 1 less assumed node component
            if union(u, v):
                components -= 1

        # overall: tc O(V + E * α(n)) =~ O(V + E)
        # overall: sc O(V)
        return components

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        # Note:
        # Find the largest connected component using an grid of land and water

        # Adjacency Matrix:

        # grid = [
        #     [0, 0, 1, 0, 0],
        #     [0, 1, 1, 1, 0],
        #     [0, 0, 1, 0, 0],
        #     [0, 0, 0, 0, 0],
        # ]

        # Backtracking vs Recursion for Graph Traversal:

        # Recursion:
        #   - is a concept, backtracking is a technique using that concept.
        #   - does not imply backtracking 

        # Backtracking:
        #   - must use recursion.
        #   - requires reverting state (e.g., path.pop()) to explore alternatives.

        # This problem uses recursion, 
        # but is not backtracking since once land is sunk (set to 0),
        # it is never restored/we never backtracking via a pop()),
        # since we are performing a flood fill traversal.

        # Recursive Flood Fill (DFS Traversal):
        # 1. Iterate over entire grid
        # 2. When we hit a land cell, we have found a new connected component
        # 3. Explore while changing land as water to mark as visited
        # 4. Continue exploring entire grid 

        # Empty check:
        # no grid exists, no connected components
        if grid == None:
            return 0

        # Grid Traversal:
        # sc: O(1)
        m, n = len(grid), len(grid[0])

        # global max connected Component
        # sc: O(1)
        maxArea = 0

        def dfs(r: int, c: int) -> int:

            # Late Pruning:
            # skip if cell is out of bounds or water
            # tc: O(1)
            if (r < 0 or r >= m or 
                c < 0 or c >= n or
                grid[r][c] == 0):
                return 0

            # Process Root:
            # turn land into water, which marks the cell as visited
            grid[r][c] = 0

            # Track size for current island
            area = 1

            # Explore Neighbors: 
            # look for connected land to current island and sink
            area += dfs(r + 1, c)
            area += dfs(r - 1, c)
            area += dfs(r, c + 1)
            area += dfs(r, c - 1)

            # Return area to root call
            return area
    
        # Iterate over grid
        # tc: O(r*c)
        for r in range(m):
            for c in range(n):

                # New Island Found
                # explore new connected component
                # tc: O(1)
                if grid[r][c] == 1:

                    # grab area for connected component
                    islandArea = dfs(r, c)

                    # compare area to max
                    maxArea = max(maxArea, islandArea)

        # overall: tc O(r*c)
        # overall: sc O(r*c)
        return maxArea

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        # Recursive Flood Fill (BFS Traversal):
        # 1. Iterate over entire grid
        # 2. When we hit a land cell, we have found a new connected component
        # 3. Explore while changing land as water to mark as visited and add to deque
        # 4. Continue exploring entire grid 

        # Empty Check: no islands, grid is empty
        # tc: O(1)
        if not grid:
            return 0

        # Grid Traversal
        m, n = len(grid), len(grid[0])

        # Tracking global max island
        maxArea = 0


        def bfs(r, c):

            # area count for local island
            area = 0

            # Iterative BFS Queue
            # sc: O(r*c)
            queue = deque()

            # Add root land to queue execution and mark as visited
            queue.append((r, c))
            grid[r][c] = 0

            # While we have land in current connected component
            while queue:

                # Pop a land cell
                cr, cc = queue.popleft()

                # Add to island size
                area += 1

                # Explore Neighbors:
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:

                    # next neighbor
                    nr, nc = cr + dr, cc + dc

                    # Early Pruning:
                    # only enqueue if in bounds and land
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:

                        # Add root land to queue execution and mark as visited
                        queue.append((nr, nc))
                        grid[nr][nc] = 0

            # Return:
            # pass area to root call
            return area


        # Iterate over grid
        # tc: O(r*c)
        for r in range(m):
            for c in range(n):

                # Found a new connected component
                if grid[r][c] == 1:

                    # grab area for connected component
                    islandArea = bfs(r, c)

                    # compare area to max
                    maxArea = max(maxArea, islandArea)


        # overall: tc O(m*n)
        # overall: sc O(m*n)
        return maxArea

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        # Note:
        # Union-Find approach to track connected components by size

        # Recursive Flood Fill Via Connected Components (Union Find Traversal):
        # 1. Iterate over entire grid
        # 2. When we hit a land cell, we have found a new connected component
        # 3. Explore while changing land as water to mark as visited and add to deque
        # 4. Continue exploring entire grid 

        # Empty Check: no islands, grid is empty
        # tc: O(1)
        if not grid:
            return 0

        # Grid Traversal
        m, n = len(grid), len(grid[0])

        # Union Find Data Structure
        # sc: O(r*c) 
        parent = {}
        size = {}

        # Iterate all grid
        # tc: O(r*c)
        for r in range(m):
            for c in range(n):

                # Add land cell to union find data structure
                if grid[r][c] == 1:
                    parent[(r, c)] = (r, c)
                    size[(r, c)] = 1

        # Find():
        # with Path Compression
        # tc: O(α(n)) amortized per call
        # sc: O(1) per call
        def find(x):

            # Path Compression
            if parent[x] != x:
                parent[x] = find(parent[x])

            return parent[x]

        # Union by Size
        # tc: O(α(n)) amortized
        # sc: O(1)
        def union(x, y):
            
            # Ignore if nodes share the same root (same connected component)
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return
            
            # Smaller subtree will join the larger subtree
            # tc: O(1)
            if size[rootX] >= size[rootY]:
                parent[rootY] = rootX

                # Add to size
                size[rootX] += size[rootY]
            else:
                parent[rootX] = rootY
                size[rootY] += size[rootX]


        # Iterate over grid
        # tc: O(r*c)
        for r in range(m):
            for c in range(n):

                # New connected component found
                if grid[r][c] == 1:

                    # Explore Down and Right Neighbors:
                    # The rest will be explored as we iterate and Union
                    for dr, dc in [(1,0), (0,1)]:
                        nr, nc = r + dr, c + dc

                        # Early Pruning:
                        # only union if in bounds and land
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                            union((r, c), (nr, nc))

        # Grab max island
        largestIsland = max(size.values(), default=0)

        # overall: tc O(r*c * α(r*c)) =~ O(r*c)
        # overall: sc O(r*c)
        return largestIsland

    def solve(self, board: List[List[str]]) -> None:
        
        # Identify Safe 'O's
        #   1. Any 'O' that touches a border cannot be flipped
        #   2. Any 'O' connected (directly or indirectly) to a border 'O' is safe
        #       - An 'O' connected to another 'O' cannot be fully surrounded by 'X'
        #   3. So we can mark islands starting from the outer 'O' and fill them,
        #      marking them as cannot be captured
        #   4. Any other 'O' is thus able to be captured

        # Starting DFS/BFS From Border 'O's:
        # Any 'O' that is connected to the border cannot be captured

        # Note:
        # 1. Any 'O' connected to the border cannot be captured.
        # 2. Mark all border-connected 'O's with DFS (temporary marker 'T').
        # 3. After traversal:
        #    Flip all remaining 'O' to 'X' (they are surrounded).
        #    Flip all 'T' back to 'O'.
        # 4. Mutates board in-place, no return required.

        # Empty Check
        # tc: O(1), sc: O(1)
        if not board:
            return

        # Grid dimensions
        # sc: O(1)
        m, n = len(board), len(board[0])

        # Recursive DFS traversal: mark border-connected 'O's
        # sc: O(m*n) recursion stack worst-case
        def dfs(r, c):

            # Early Pruning:
            # skip if out of bounds or not an 'O'
            # tc: O(1)
            if (r < 0 or r >= m or 
                c < 0 or c >= n or
                board[r][c] != 'O'):
                return

            # Process Root:
            # mark current cell as safe and not able to be captured
            # tc: O(1), sc: O(1)
            board[r][c] = 'T'

            # Explore:
            # recursively visit all neighbors, to see if we find safe 'O's unable to be captured
            # tc: O(r*c)
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        # Process Roots:
        # Start DFS from border 'O's
        # tc: O(r+c)
        for i in range(m):
            
            # left column
            dfs(i, 0)
            
            # right column
            dfs(i, n - 1)

        for j in range(n):
            
            # top row
            dfs(0, j)

            # bottom row
            dfs(m - 1, j)

        # Late Prune:
        # Flip surrounded 'O' -> 'X', revert 'T' -> 'O'
        # tc: O(r*c)
        for i in range(m):
            for j in range(n):

                # Any 'O' not marked as safe will be captured
                if board[i][j] == 'O':
                    board[i][j] = 'X'

                # Any 'T' is safe and will be reverted to 'O'
                elif board[i][j] == 'T':
                    board[i][j] = 'O'

        # overall: tc O(m * n)
        # overall: sc O(m * n)

    def solve(self, board: List[List[str]]) -> None:
        
        # Identify Safe 'O's
        #   1. Any 'O' that touches a border cannot be flipped
        #   2. Any 'O' connected (directly or indirectly) to a border 'O' is safe
        #       - An 'O' connected to another 'O' cannot be fully surrounded by 'X'
        #   3. So we can mark islands starting from the outer 'O' and fill them,
        #      marking them as cannot be captured
        #   4. Any other 'O' is thus able to be captured

        # Starting DFS/BFS From Border 'O's:
        # Any 'O' that is connected to the border cannot be captured

        # Note:
        # 1. Any 'O' connected to the border cannot be captured.
        # 2. Mark all border-connected 'O's with DFS (temporary marker 'T').
        # 3. After traversal:
        #    Flip all remaining 'O' to 'X' (they are surrounded).
        #    Flip all 'T' back to 'O'.
        # 4. Mutates board in-place, no return required.

        # Empty Check
        # tc: O(1), sc: O(1)
        if not board:
            return

        # Grid dimensions
        # sc: O(1)
        m, n = len(board), len(board[0])

        # Recursive DFS traversal: mark border-connected 'O's
        # sc: O(m*n) recursion stack worst-case
        def bfs(r, c):

            # Iterative Queue
            # sc: O(r*c)
            queue = deque([])

            # Process Root:
            # initialize BFS from this cell
            # tc: O(1)
            queue.append((r, c))
            board[r][c] = 'T'
            
            # While we still have 'O' connected to the root 'O'
            # tc: O(r*c)
            while queue:

                # Grab the root 'O' (original edge 'O')
                cr, cc = queue.popleft()

                # Process Candidates:
                # recursively explore neighbors
                # tc: O(r*c)
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = cr + dr, cc + dc

                    # Early Prune:
                    # only recurse if valid bounds and 'O'

                    if (0 <= nr < m and 
                        0 <= nc < n and 
                        board[nr][nc] == 'O'):

                        # Mark '0' as safe
                        # tc: O(1)
                        board[nr][nc] = 'T'

                        # Append 'O' neighbor to stack for processing
                        # tc: O(1)
                        queue.append((nr, nc))

        # Process Roots:
        # Start DFS from border 'O's
        # tc: O(r+c)
        for i in range(m):

            # left column
            if board[i][0] == 'O':
                bfs(i, 0)

            # right column
            if board[i][n - 1] == 'O':
                bfs(i, n - 1)

        for j in range(n):

            # top row
            if board[0][j] == 'O':
                bfs(0, j)

            # bottom row
            if board[m - 1][j] == 'O':
                bfs(m - 1, j)

        # Late Prune:
        # Flip surrounded 'O' -> 'X', revert 'T' -> 'O'
        # tc: O(r*c)
        for i in range(m):
            for j in range(n):

                # Any 'O' not marked as safe will be captured
                if board[i][j] == 'O':
                    board[i][j] = 'X'

                # Any 'T' is safe and will be reverted to 'O'
                elif board[i][j] == 'T':
                    board[i][j] = 'O'

        # overall: tc O(m * n)
        # overall: sc O(m * n)

    def solve(self, board: List[List[str]]) -> None:
        
        # Identify Safe 'O's
        #   1. Any 'O' that touches a border cannot be flipped
        #   2. Any 'O' connected (directly or indirectly) to a border 'O' is safe
        #       - An 'O' connected to another 'O' cannot be fully surrounded by 'X'
        #   3. So we can mark islands starting from the outer 'O' and fill them,
        #      marking them as cannot be captured
        #   4. Any other 'O' is thus able to be captured

        # Starting DFS/BFS From Border 'O's:
        # Any 'O' that is connected to the border cannot be captured

        # Connected Components / Union Find
        # Treat each 'O' as a node
        # Create a dummy node representing the border
        # 1. Union all border 'O's with dummy node (safe)
        # 2. Union all adjacent 'O's (up/down/left/right)
        # 3. Any 'O' connected to dummy is afe
        # 4. Flip all other 'O' to 'X'

        # Empty Check
        # tc: O(1), sc: O(1)
        if not board:
            return

        # Grid dimensions
        # sc: O(1)
        m, n = len(board), len(board[0])

        # Parent dictionary for Union-Find
        # sc: O(m*n)
        parent = {}

        # Find with Path Compression
        # tc: O(α(N)) amortized
        def find(x: int) -> int:

            parent.setdefault(x, x)
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        # Union two sets
        # tc: O(α(N)) amortized, sc: O(1)
        def union(x: int, y: int) -> None:
            parent[find(x)] = find(y)

        # Special integer representing 'border'
        # all border nodes will be Union() with it
        # sc: O(1)
        dummy = m * n 

        # Process Roots and Candidates:
        # iterate all cells, union border 'O's and neighbor 'O's
        # tc: O(m*n)
        for r in range(m):
            for c in range(n):

                if board[r][c] == 'O':

                    # Grid coordinate converted into an integer
                    # (0, 0) => 0
                    # (0, 1) => 1
                    # (1, 0) => 4
                    # fn() = 
                    idx = r * n + c

                    # Check: if 'O' has a coordinate on either edge of the grid
                    # Implies: this 'O' is a border 'O'
                    if r in (0, m - 1) or c in (0, n - 1):

                        # Union border 'O's with dummy 'border'
                        union(idx, dummy)

                    # Union adjacent 'O's
                    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                        nr, nc = r + dr, c + dc

                        # Early Exit: 
                        if (0 <= nr < m and 
                            0 <= nc < n and 
                            board[nr][nc] == 'O'):
                            
                            # Calculate neighbor index
                            neighborIndex = nr * n + nc

                            union(idx, neighborIndex)

        # Late Prune:
        # flip 'O' not connected to dummy -> 'X'
        # tc: O(m*n * α(N)) amortized, sc: O(1) extra
        for r in range(m):
            for c in range(n):
                if board[r][c] == 'O' and find(r * n + c) != find(dummy):
                    board[r][c] = 'X'

        # overall: tc O(m*n * α(m*n)) =~ O(m*n)
        # overall: sc (m*n)

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

        # Connected Components in a Graph:
        # Each edge adds a connection between two nodes.
        # A redundant connection is the first edge that forms a cycle.
        # We can detect this by checking if two nodes are already connected before adding the edge.

        # Graph representation using adjacency list
        # sc: O(V + E)
        graph = defaultdict(list)
        
        # tc: O(V + E)
        # sc: O(V)
        def dfs(u, target, visited):

            # path exists => adding edge would form a cycle
            if u == target:
                return True

            # mark as visited
            visited.add(u)
            for v in graph[u]:
                if v not in visited and dfs(v, target, visited):
                    return True
            return False
        
        # Process edges one by one
        # tc: O(E * V) worst-case (each DFS may traverse all nodes)
        # sc: O(V + E)
        for u, v in edges:

            visited = set()

            # Check if u and v are already connected
            # If yes, adding this edge forms a cycle -> redundant
            if u in graph and v in graph and dfs(u, v, visited):
                return [u, v]

            # Otherwise, add edge to graph
            graph[u].append(v)
            graph[v].append(u)

        # overall: tc O(E * V)
        # overall: sc O(V + E) 

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        
        # Graph representation
        # sc: O(V + E)
        graph = defaultdict(list)
        
        # BFS Helper Function
        # tc: O(V + E) worst-case per call
        # sc: O(V) for queue + visited
        def bfs(u, target):

            # tracking visited per BFS
            visited = set([u])

            # Iterative queue
            queue = deque([u])

            # While we still have connected nodes
            while queue:

                # Grab root node
                node = queue.popleft()

                # Process Root:
                # path exists, adding edge would form a cycle
                if node == target:
                    return True

                # Explore:
                # recursively explore neighbors                
                for nei in graph[node]:

                    # Early Prune:
                    # explore if not visited before
                    if nei not in visited:
                        
                        # Process root:
                        # mark as visited
                        visited.add(nei)

                        # Append to queue to process
                        queue.append(nei)
            return False
        

        # Process each edge
        # tc: O(E * V)
        # sc: O(V + E)
        for u, v in edges:

            if u in graph and v in graph and bfs(u, v):
                return [u, v]

            # Add edge to graph
            graph[u].append(v)
            graph[v].append(u)

        # overall tc: O(E * V)
        # overall sc: O(V + E)

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
       
        # Union-Find Approach:
        # Each node starts as its own parent.
        # If two nodes of an edge already share the same root, adding this edge forms a cycle.
        n = len(edges)

        parent = [0] * (n + 1)
        rank = [0] * (n + 1)

        for i in range(n + 1):
            parent[i] = i
            rank[i] = 1


        # Find with Path Compression
        # tc: O(α(n)
        def find(x):

            # if parent isn't self, recurse upwards
            if parent[x] != x:

                # path compression
                parent[x] = find(parent[x])

            # return parent of original, after path compression
            return parent[x]
        
        # Union by Rank
        # tc: O(α(n)) amortized per call, sc: O(1)
        def union(x, y):

            # cycle detected, no union performed
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return False

            # Union by rank to keep tree shallow
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1

            # Union successful
            return True
        
        # Process all edges
        # tc: O(E * α(n))
        # sc: O(n) for parent and rank
        for u, v in edges:
            if not union(u, v):

                # first edge forming a cycle is redundant
                return [u, v]
        
        # overall tc: O(E * α(n))
        # overall sc: O(n)

    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        
        # Problem:
        # Emails that belong to the same person are connected via accounts.
        # Build a graph where nodes are emails, edges connect emails in the same account.
        # Then traverse connected components using DFS to collect all emails for each person.
        
        # Graph Representation: adjacency list for emails
        # sc: O(E) where E = total number of emails
        graph = defaultdict(set)
        
        # Map email -> name
        email_to_name = {}
        
        # Build graph
        # tc: O(A * L^2) worst-case where A = number of accounts, L = emails per account
        for account in accounts:
            name = account[0]
            first_email = account[1]
            for email in account[1:]:
                graph[first_email].add(email)
                graph[email].add(first_email)
                email_to_name[email] = name

        visited = set()
        res = []

        # DFS Helper
        # tc: O(E)
        # sc: O(E) recursion stack
        def dfs(email, component):
            visited.add(email)
            component.append(email)
            for nei in graph[email]:
                if nei not in visited:
                    dfs(nei, component)

        # Traverse all emails
        # tc: O(E)
        for email in graph:
            if email not in visited:
                component = []
                dfs(email, component)
                # sort emails and prepend name
                res.append([email_to_name[email]] + sorted(component))

        # overall tc: O(A * L^2 + E log E) for sorting
        # overall sc: O(E + A * L) for graph and recursion
        return res

    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        
        # BFS Approach:
        # Build the same graph of emails connected by accounts.
        # Instead of DFS, explore each connected component level by level.

        # Graph Representation
        # sc: O(E)
        graph = defaultdict(set)
        email_to_name = {}

        # Build graph
        # tc: O(A * L^2)
        for account in accounts:
            name = account[0]
            first_email = account[1]
            for email in account[1:]:
                graph[first_email].add(email)
                graph[email].add(first_email)
                email_to_name[email] = name

        visited = set()
        res = []

        # BFS Helper
        # tc: O(E)
        # sc: O(E)
        def bfs(start):
            queue = deque([start])
            component = []
            visited.add(start)
            while queue:
                email = queue.popleft()
                component.append(email)
                for nei in graph[email]:
                    if nei not in visited:
                        visited.add(nei)
                        queue.append(nei)
            return component

        # Process all emails
        # tc: O(E)
        for email in graph:
            if email not in visited:
                component = bfs(email)
                res.append([email_to_name[email]] + sorted(component))

        # overall tc: O(A * L^2 + E log E) for sorting
        # overall sc: O(E + A * L) for graph + queue
        return res

    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        
        # Union-Find Approach:
        # Treat each email as a node.
        # Union all emails in the same account.
        # After all unions, emails in the same connected component belong to the same person.

        parent = {}
        email_to_name = {}

        # Initialize parent mapping
        for account in accounts:
            name = account[0]
            first_email = account[1]
            for email in account[1:]:
                parent[email] = email
                email_to_name[email] = name

        # Find with Path Compression
        # tc: O(α(E))
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        # Union by parent
        # tc: O(α(E))
        def union(x, y):
            parent[find(x)] = find(y)

        # Process accounts to union emails
        # tc: O(A * L * α(E))
        for account in accounts:
            first_email = account[1]
            for email in account[1:]:
                union(first_email, email)

        # Group emails by root parent
        # tc: O(E)
        groups = defaultdict(list)
        for email in parent:
            root = find(email)
            groups[root].append(email)

        # Build result
        res = []
        # tc: O(E log E) for sorting
        for root, emails in groups.items():
            res.append([email_to_name[root]] + sorted(emails))

        # overall tc: O(A * L * α(E) + E log E)
        # overall sc: O(E + A * L) for parent map and groups
        return res