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 validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        
        # Note:
        # Detecting a path between two nodes in an undirected graph
        # using an Edge List

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

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


        # DFS Path Existence Check (Undirected Graph)

        # Each node is represented as a node in an undirected graph,
        # built explicitly from the edges list. Since the graph is
        # undirected, each edge (u, v) is added in both directions.

        # DFS explores every node reachable from source, marking each
        # one visited along the way. If destination is ever reached
        # during this exploration, a path is guaranteed to exist.
        # If DFS exhausts every reachable node without finding
        # destination, no path can exist between the two.

        # Edge Case:
        # source and destination are the same node, trivially connected
        if source == destination:
            return True

        # Build Adjacency List:
        # graph[u] = neighbors of u
        # tc: O(V + 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()

        def dfs(node):

            # Early Return:
            # reached the destination, a path exists
            if node == destination:
                return True

            # Mark node as visited
            visited.add(node)

            # Explore Neighbors:
            for nei in graph[node]:

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

                    # If neighbor reaches destination, propagate success upward
                    if dfs(nei):
                        return True

            # Exhausted all neighbors without finding destination
            return False

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

    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        
        # Note:
        # Detecting a path between two nodes in an undirected graph
        # using an Edge List

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

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


        # BFS Path Existence Check (Undirected Graph)

        # Each node is represented as a node in an undirected graph,
        # built explicitly from the edges list. Since the graph is
        # undirected, each edge (u, v) is added in both directions.

        # BFS explores nodes level by level starting from source. Any
        # node dequeued that equals destination guarantees a path
        # exists. If the queue empties without ever dequeuing
        # destination, no path can exist between the two.

        # Edge Case:
        # source and destination are the same node, trivially connected
        if source == destination:
            return True

        # Build Adjacency List:
        # graph[u] = neighbors of u
        # tc: O(V + E)
        # sc: O(V + E)
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Iterative BFS Queue:
        # start from source
        # sc: O(V)
        queue = deque([source])
        visited = {source}

        while queue:

            # Pop a node from the queue
            node = queue.popleft()

            # Early Return:
            # reached the destination, a path exists
            if node == destination:
                return True

            # Explore Neighbors:
            for nei in graph[node]:

                # Early Pruning:
                # only queue node if not already visited
                if nei not in visited:

                    visited.add(nei)
                    queue.append(nei)

        # Exhausted all reachable nodes without finding destination

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

    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        
        # Note:
        # Detecting a path between two nodes in an undirected graph
        # using an Edge List

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

        # Unlike DFS/BFS, Union-Find operates directly on the Edge List —
        # there's no need to build an Adjacency List first, since we only
        # ever process one edge (pair of nodes) at a time.


        # Union-Find (Disjoint Set) for Path Existence in Undirected Graph

        # Each node starts as its own disjoint set. Processing an edge
        # (u, v) unions the sets containing u and v, merging any two
        # nodes directly connected by an edge into the same component.

        # After processing every edge, a path exists between source and
        # destination if and only if they share the same root, meaning
        # they ended up in the same connected component.

        # Initialize Parent + Rank Arrays:
        # parent[i] = representative of the set containing node i
        # rank[i] = size/depth heuristic for union by rank
        # tc: O(V)
        # sc: O(V)
        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:
            # already in the same set, nothing to merge
            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, bump rank to mark X the higher rank tree
                rank[rootX] += 1

        # Process All Edges:
        # tc: O(E * α(V))
        for u, v in edges:
            union(u, v)

        # A path exists if and only if source and destination
        # share the same root, meaning they're in the same component
        # tc: O(α(V))

        # overall: tc O((V + E) * α(V))
        # overall: sc O(V)
        return find(source) == find(destination)

    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 numIslands(self, grid: List[List[str]]) -> int:
        
        # Note:
        # Counting the number of connected components
        # using a Grid

        # Grid:
        # grid = [
        #     ["1","1","0","0"],
        #     ["1","1","0","0"],
        #     ["0","0","1","0"],
        #     ["0","0","0","1"],
        # ]

        # Unlike Edge List / Adjacency List problems, the grid itself
        # is the graph, a cell's neighbors are always just its 4
        # grid-adjacent cells. No preprocessing is needed to build an
        # adjacency structure, same as Nearest Exit and Max Area of Island.


        # DFS Grid Traversal to Count Connected Components (Islands)

        # By representing land cells as nodes in a graph, we can use DFS
        # to explore every connected land cell starting from any unvisited
        # land cell. Each fresh DFS call that starts from an unvisited
        # land cell represents the discovery of one new island, since DFS
        # will mark every cell connected to it as visited before returning.

        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])

        # 4 cardinal directions
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Track visited land cells to avoid revisiting
        # sc: O(V)
        visited = set()

        def dfs(row, col):

            # Explore Neighbors:
            for dr, dc in directions:

                nr, nc = row + dr, col + dc

                # Bounds Check:
                if 0 <= nr < rows and 0 <= nc < cols:

                    # Early Pruning:
                    # only recurse into cell if:
                    # - it's land ('1')
                    # - not already visited
                    if grid[nr][nc] == '1' and (nr, nc) not in visited:

                        visited.add((nr, nc))
                        dfs(nr, nc)

        # Track number of connected components (islands)
        islands = 0

        # Run DFS for each unvisited land cell,
        # which will mark all connected land cells by adding them to visited
        # tc: O(V), each cell is visited and processed at most once overall
        for row in range(rows):
            for col in range(cols):

                # New island has been found
                if grid[row][col] == '1' and (row, col) not in visited:

                    visited.add((row, col))
                    dfs(row, col)
                    islands += 1

        # overall: tc O(m * n), each cell is visited at most once
        # overall: sc O(m * n), for the visited set and recursion stack
        #   in the worst case of one giant island
        return islands

    def numIslands(self, grid: List[List[str]]) -> int:
        
        # Note:
        # Counting the number of connected components
        # using a Grid

        # Grid:
        # grid = [
        #     ["1","1","0","0"],
        #     ["1","1","0","0"],
        #     ["0","0","1","0"],
        #     ["0","0","0","1"],
        # ]

        # Unlike Edge List / Adjacency List problems, the grid itself
        # is the graph, a cell's neighbors are always just its 4
        # grid-adjacent cells. No preprocessing is needed to build an
        # adjacency structure, same as Nearest Exit and Max Area of Island.


        # BFS Grid Traversal to Count Connected Components (Islands)

        # By representing land cells as nodes in a graph, we can use BFS
        # to explore every connected land cell starting from any unvisited
        # land cell. Each fresh BFS call that starts from an unvisited
        # land cell represents the discovery of one new island, since BFS
        # will mark every cell connected to it as visited before the
        # queue empties.

        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])

        # 4 cardinal directions
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Track visited land cells to avoid revisiting
        # sc: O(V)
        visited = set()

        def bfs(row, col):

            # Iterative BFS Queue:
            queue = deque([(row, col)])

            while queue:

                # Pop a cell from the queue
                r, c = queue.popleft()

                # Explore Neighbors:
                for dr, dc in directions:

                    nr, nc = r + dr, c + dc

                    # Bounds Check:
                    if 0 <= nr < rows and 0 <= nc < cols:

                        # Early Pruning:
                        # only queue cell if:
                        # - it's land ('1')
                        # - not already visited
                        if grid[nr][nc] == '1' and (nr, nc) not in visited:

                            visited.add((nr, nc))
                            queue.append((nr, nc))

        # Track number of connected components (islands)
        islands = 0

        # Run BFS for each unvisited land cell,
        # which will mark all connected land cells by adding them to visited
        # tc: O(V), each cell is visited and processed at most once overall
        for row in range(rows):
            for col in range(cols):

                # New island has been found
                if grid[row][col] == '1' and (row, col) not in visited:

                    visited.add((row, col))
                    bfs(row, col)
                    islands += 1

        # overall: tc O(m * n), each cell is visited at most once
        # overall: sc O(m * n), for the visited set and queue
        #   in the worst case of one giant island
        return islands

    def numIslands(self, grid: List[List[str]]) -> int:
        
        # Note:
        # Counting the number of connected components
        # using a Grid

        # Grid:
        # grid = [
        #     ["1","1","0","0"],
        #     ["1","1","0","0"],
        #     ["0","0","1","0"],
        #     ["0","0","0","1"],
        # ]

        # Unlike Edge List / Adjacency List problems, the grid itself
        # is the graph, a cell's neighbors are always just its 4
        # grid-adjacent cells. Union-Find operates directly on the grid,
        # merging each land cell with its land neighbors as it scans.


        # Union-Find (Disjoint Set) to Count Connected Components (Islands)

        # Each land cell starts as its own disjoint set, flattened from
        # its (row, col) position into a single index (row * cols + col).
        # Scanning the grid and unioning each land cell with its land
        # neighbors (only right and down needed, since left/up are
        # covered by earlier cells scanning forward) merges every
        # connected island into a single component. The final answer is
        # the number of unique land roots remaining.

        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])

        # Initialize Parent + Rank Arrays:
        # flatten (row, col) into a single index: row * cols + col
        # tc: O(V)
        # sc: O(V)
        parent = list(range(rows * cols))
        rank = [0] * (rows * cols)

        # 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
                rank[rootX] += 1

        # Track total land cells found, needed since parent starts
        # with every grid cell (including water) as its own set
        landCells = set()

        # Process Grid:
        # only union land cells with their land neighbors (right, down)
        # tc: O(V)
        for row in range(rows):
            for col in range(cols):

                if grid[row][col] == '1':

                    landCells.add(row * cols + col)

                    # Explore Neighbors:
                    # only check right and down, left/up are handled
                    # when those earlier cells were processed
                    for dr, dc in [(1, 0), (0, 1)]:

                        nr, nc = row + dr, col + dc

                        if (0 <= nr < rows and 0 <= nc < cols and
                            grid[nr][nc] == '1'):

                            union(row * cols + col, nr * cols + nc)

        # Count the number of unique roots among land cells only,
        # which corresponds to the number of islands
        roots = set()
        for cell in landCells:
            roots.add(find(cell))

        # overall: tc O(V * α(V))
        # overall: sc O(V)
        return len(roots)

    def closedIsland(self, grid: List[List[int]]) -> int:
        
        # Note:
        # Counting connected components that don't touch the border
        # using a Grid

        # Grid (0 = land, 1 = water):
        # grid = [
        #     [1,1,1,1,1,1,1],
        #     [1,0,0,0,0,0,1],
        #     [1,0,1,0,1,0,1],
        #     [1,0,0,0,0,0,1],
        #     [1,1,1,1,1,1,1],
        # ]

        # Unlike Edge List / Adjacency List problems, the grid itself
        # is the graph, a cell's neighbors are always just its 4
        # grid-adjacent cells. No preprocessing is needed to build an
        # adjacency structure, same as Number of Islands.

        # Note the flipped values compared to Number of Islands:
        # here 0 = land, 1 = water, so we're counting connected
        # components of 0s instead of 1s.


        # DFS Grid Traversal to Count Closed Islands

        # An island is only "closed" if none of its land cells touch
        # the grid's outer border, since any land cell on the border
        # means the island leaks out to the edge of the map and is
        # therefore not fully surrounded by water.

        # DFS explores every connected land cell starting from an
        # unvisited land cell, and tracks whether that exploration ever
        # touches a border cell. If it never does, the entire connected
        # component is safely enclosed and counts as one closed island.

        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])

        # 4 cardinal directions
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Track visited land cells to avoid revisiting
        # sc: O(V)
        visited = set()

        def dfs(row, col):

            # Track Border Contact:
            # this cell touching the border means the island isn't closed
            touchesBorder = (row == 0 or row == rows - 1 or
                              col == 0 or col == cols - 1)

            # Explore Neighbors:
            for dr, dc in directions:

                nr, nc = row + dr, col + dc

                # Bounds Check:
                if 0 <= nr < rows and 0 <= nc < cols:

                    # Early Pruning:
                    # only recurse into cell if:
                    # - it's land (0)
                    # - not already visited
                    if grid[nr][nc] == 0 and (nr, nc) not in visited:

                        visited.add((nr, nc))

                        # Propagate Border Contact:
                        # if any neighbor touches the border, the whole
                        # island is disqualified regardless of this cell
                        if dfs(nr, nc):
                            touchesBorder = True

            return touchesBorder

        # Track number of closed islands
        closedIslands = 0

        # Run DFS for each unvisited land cell,
        # which will mark all connected land cells by adding them to visited
        # tc: O(V), each cell is visited and processed at most once overall
        for row in range(rows):
            for col in range(cols):

                # New island has been found
                if grid[row][col] == 0 and (row, col) not in visited:

                    visited.add((row, col))

                    # Only count as closed if DFS never touched the border
                    if not dfs(row, col):
                        closedIslands += 1

        # overall: tc O(m * n), each cell is visited at most once
        # overall: sc O(m * n), for the visited set and recursion stack
        #   in the worst case of one giant island
        return closedIslands

    def closedIsland(self, grid: List[List[int]]) -> int:
        
        # Note:
        # Counting connected components that don't touch the border
        # using a Grid

        # Grid (0 = land, 1 = water):
        # grid = [
        #     [1,1,1,1,1,1,1],
        #     [1,0,0,0,0,0,1],
        #     [1,0,1,0,1,0,1],
        #     [1,0,0,0,0,0,1],
        #     [1,1,1,1,1,1,1],
        # ]

        # Unlike Edge List / Adjacency List problems, the grid itself
        # is the graph, a cell's neighbors are always just its 4
        # grid-adjacent cells. No preprocessing is needed to build an
        # adjacency structure, same as Number of Islands.

        # Note the flipped values compared to Number of Islands:
        # here 0 = land, 1 = water, so we're counting connected
        # components of 0s instead of 1s.


        # BFS Grid Traversal to Count Closed Islands

        # An island is only "closed" if none of its land cells touch
        # the grid's outer border, since any land cell on the border
        # means the island leaks out to the edge of the map and is
        # therefore not fully surrounded by water.

        # BFS explores every connected land cell starting from an
        # unvisited land cell, and tracks whether that exploration ever
        # touches a border cell. If it never does, the entire connected
        # component is safely enclosed and counts as one closed island.

        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])

        # 4 cardinal directions
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Track visited land cells to avoid revisiting
        # sc: O(V)
        visited = set()

        def bfs(row, col):

            # Track Border Contact:
            # starting cell touching the border means the island isn't closed
            touchesBorder = (row == 0 or row == rows - 1 or
                              col == 0 or col == cols - 1)

            # Iterative BFS Queue:
            queue = deque([(row, col)])

            while queue:

                # Pop a cell from the queue
                r, c = queue.popleft()

                # Explore Neighbors:
                for dr, dc in directions:

                    nr, nc = r + dr, c + dc

                    # Bounds Check:
                    if 0 <= nr < rows and 0 <= nc < cols:

                        # Early Pruning:
                        # only queue cell if:
                        # - it's land (0)
                        # - not already visited
                        if grid[nr][nc] == 0 and (nr, nc) not in visited:

                            visited.add((nr, nc))

                            # Track Border Contact:
                            if (nr == 0 or nr == rows - 1 or
                                nc == 0 or nc == cols - 1):
                                touchesBorder = True

                            queue.append((nr, nc))

            return touchesBorder

        # Track number of closed islands
        closedIslands = 0

        # Run BFS for each unvisited land cell,
        # which will mark all connected land cells by adding them to visited
        # tc: O(V), each cell is visited and processed at most once overall
        for row in range(rows):
            for col in range(cols):

                # New island has been found
                if grid[row][col] == 0 and (row, col) not in visited:

                    visited.add((row, col))

                    # Only count as closed if BFS never touched the border
                    if not bfs(row, col):
                        closedIslands += 1

        # overall: tc O(m * n), each cell is visited at most once
        # overall: sc O(m * n), for the visited set and queue
        #   in the worst case of one giant island
        return closedIslands

    def closedIsland(self, grid: List[List[int]]) -> int:
        
        # Note:
        # Counting connected components that don't touch the border
        # using a Grid

        # Grid (0 = land, 1 = water):
        # grid = [
        #     [1,1,1,1,1,1,1],
        #     [1,0,0,0,0,0,1],
        #     [1,0,1,0,1,0,1],
        #     [1,0,0,0,0,0,1],
        #     [1,1,1,1,1,1,1],
        # ]

        # Unlike Edge List / Adjacency List problems, the grid itself
        # is the graph, a cell's neighbors are always just its 4
        # grid-adjacent cells. Union-Find operates directly on the grid,
        # merging each land cell with its land neighbors as it scans.


        # Union-Find (Disjoint Set) to Count Closed Islands

        # Every land cell starts as its own disjoint set, flattened from
        # its (row, col) position into a single index (row * cols + col).
        # A single extra sentinel index represents "the border" itself.
        # Any land cell sitting on the border is unioned directly into
        # this sentinel, so every island that leaks out to the edge
        # collapses into the same shared border component.

        # After processing every cell, the final answer is the number
        # of unique land roots that are NOT the border's root.

        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])

        # Initialize Parent + Rank Arrays:
        # flatten (row, col) into a single index: row * cols + col
        # one extra slot at the end reserved as the border sentinel
        # tc: O(V)
        # sc: O(V)
        border = rows * cols
        parent = list(range(rows * cols + 1))
        rank = [0] * (rows * cols + 1)

        # 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
                rank[rootX] += 1

        # Process Grid:
        # union land cells with their land neighbors (right, down),
        # and union any border-touching land cell with the sentinel
        # tc: O(V)
        for row in range(rows):
            for col in range(cols):

                if grid[row][col] == 0:

                    cell = row * cols + col

                    # Border Sentinel:
                    # merge this cell into the shared border component
                    if row == 0 or row == rows - 1 or col == 0 or col == cols - 1:
                        union(cell, border)

                    # Explore Neighbors:
                    # only check right and down, left/up are handled
                    # when those earlier cells were processed
                    for dr, dc in [(1, 0), (0, 1)]:

                        nr, nc = row + dr, col + dc

                        if (0 <= nr < rows and 0 <= nc < cols and
                            grid[nr][nc] == 0):

                            union(cell, nr * cols + nc)

        # Count Closed Islands:
        # unique land roots that are NOT part of the border's component
        # tc: O(V * α(V))
        roots = set()
        for row in range(rows):
            for col in range(cols):

                if grid[row][col] == 0:

                    root = find(row * cols + col)

                    if root != find(border):
                        roots.add(root)

        # overall: tc O(V * α(V))
        # overall: sc O(V)
        return len(roots)

    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)