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 islandPerimeter(self, grid: List[List[int]]) -> int:
        
        # Problem:
        # Each land cell contributes 4 edges.
        #
        # But:
        # If two land cells are adjacent,
        # they share one edge.
        # That shared edge removes 2 perimeter edges
        # (one from each cell).
        #
        # Therefore:
        # For each land cell:
        #   Start with 4 sides
        #   Subtract 1 for each adjacent land neighbor
        #
        # Since each shared edge is counted twice
        # (once per cell), subtracting per neighbor
        # naturally handles correct perimeter.
        
        
        rows = len(grid)
        cols = len(grid[0])
        
        perimeter = 0
        
        # Iterate through entire grid
        # tc: O(rows * cols)
        for r in range(rows):
            for c in range(cols):
                
                # Only process land cells
                if grid[r][c] == 1:
                    
                    # Each land cell starts with 4 sides
                    perimeter += 4
                    
                    # Check top neighbor
                    if r > 0 and grid[r - 1][c] == 1:
                        perimeter -= 1
                    
                    # Check bottom neighbor
                    if r < rows - 1 and grid[r + 1][c] == 1:
                        perimeter -= 1
                    
                    # Check left neighbor
                    if c > 0 and grid[r][c - 1] == 1:
                        perimeter -= 1
                    
                    # Check right neighbor
                    if c < cols - 1 and grid[r][c + 1] == 1:
                        perimeter -= 1
        
        # overall: tc O(rows * cols)
        # overall: sc O(1)
        return perimeter

    def isAlienSorted(self, words: List[str], order: str) -> bool:
        
        # Problem:
        # We are given a custom alphabet ordering.
        # We must verify that words are sorted lexicographically
        # according to this alien order.
        #
        # Strategy:
        # 1. Convert 'order' into a rank map:
        #       char -> index (its position in alien alphabet)
        #
        # 2. Compare each adjacent pair of words.
        #    If every adjacent pair is valid,
        #    then the whole list is sorted.
        
        
        # Step 1: Build ranking map
        # tc O(26), sc O(26)
        rank = {char: i for i, char in enumerate(order)}
        
        
        # Step 2: Compare adjacent word pairs
        # tc O(total characters across words)
        for i in range(len(words) - 1):
            
            word1 = words[i]
            word2 = words[i + 1]
            
            # Compare characters lexicographically
            min_length = min(len(word1), len(word2))
            
            valid_order = False
            
            for j in range(min_length):
                
                if word1[j] != word2[j]:
                    
                    # If alien rank of word1 char is greater,
                    # ordering is invalid
                    if rank[word1[j]] > rank[word2[j]]:
                        return False
                    
                    # Correct order found, stop comparing
                    valid_order = True
                    break
            
            # If all compared chars are same,
            # then shorter word must come first
            if not valid_order:
                if len(word1) > len(word2):
                    return False
        
        # All pairs valid
        # overall tc O(N * L)
        # overall sc O(1)
        return True

    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        
            # Edge Case
            if n == 1 and not trust:
                return 1
            
            # trust_score[i] =
            #   +1 for every person who trusts i
            #   -1 for every person i trusts
            trust_score = [0] * (n + 1)
            
            # tc O(m)
            for a, b in trust:
                trust_score[a] -= 1
                trust_score[b] += 1
            
            # Judge must have score n - 1
            # tc O(n)
            for person in range(1, n + 1):
                if trust_score[person] == n - 1:
                    return person
            
            return -1

    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        
        # Edge Case:
        # If n == 1 and no trust relationships,
        # that single person is the judge.
        if n == 1 and not trust:
            return 1
        
        # indegree[i]  = how many people trust i
        # outdegree[i] = how many people i trusts
        indegree = [0] * (n + 1)
        outdegree = [0] * (n + 1)
        
        # Process trust relationships
        # tc O(len(trust))
        for a, b in trust:
            outdegree[a] += 1
            indegree[b] += 1
        
        # Find candidate
        # Judge must have:
        #   indegree == n - 1
        #   outdegree == 0
        for person in range(1, n + 1):
            if indegree[person] == n - 1 and outdegree[person] == 0:
                return person
        
        return -1

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        
        # DFS - Connected Components
         
        # Idea:
        #   - Each city = node
        #   - isConnected[i][j] = edge
        #   - Count connected components

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

        # visit all cities connected to current city
        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)

        # iterate through all cities
        for city in range(n):
            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:
        
        # BFS - Connected Components

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

        def bfs(start):

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

            while queue:
                city = queue.popleft()

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

                        visited.add(nei)   # Early marking
                        queue.append(nei)

        # scan all cities
        for city in range(n):
            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:
        
        # Union Find - Connected Components

        n = len(isConnected)

        parent = list(range(n))
        rank = [0] * n

        # Find with path compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        # Union by rank
        def union(x, y):
            rootX, rootY = find(x), find(y)

            # Early pruning:
            if rootX == rootY:
                return

            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1

        # Only check upper triangle (optimization)
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)

        # count unique roots
        roots = set(find(i) for i in range(n))

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

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

        # Connected Components In A Graph:
        # This problem is equivalent to finding out the number of connected components in a graph
        # Each land cell ('1') is a node, and edges exist between two nodes if they
        # are adjacent vertically or horizontally

        # Connected Components In A Grid Graph:
        # This problem is equivalent to finding the largest connected component
        # in a graph where:
        #   - Nodes: land cells (value = 1)
        #   - Edges: adjacency in 4 directions (up, down, left, right)

        # Backtracking vs Recursive Graph Traversal:
        # Recursion is a concept, backtracking is a technique using it.
        # Recursion does not imply backtracking.
        # Backtracking 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 are performing a flood fill traversal.

        # Recursive Flood Fill (DFS Traversal):
        # 0. Late Pruning: skip if out of bounds or water
        # 1. Process Root: sink current land cell and count it
        # 2. Explore: recursively visit all 4 neighbors
        # 3. Return: return total area of the connected component
        # Result: track and return the maximum island area

        # Empty check
        # tc: O(1)
        if not grid:
            return 0

        # sc: setting up search space rows [0, n-1] and columns [0 n-1] O(1)
        m, n = len(grid), len(grid[0])

        # Tracking Global Max Island
        # sc: O(1)
        max_area = 0

        def dfs_SinkVisitedIsland(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, 'marking' current cell as visited
            # tc: O(1), sc: O(1)
            grid[r][c] = 0

            # Process Root:
            # Track size for current island
            area = 1

            # Process Choices:
            # Explore neighbors, see if there is land to add for current island
            # and sink said neighbors
            area += dfs(r + 1, c)
            area += dfs(r - 1, c)
            area += dfs(r, c + 1)
            area += dfs(r, c - 1)

            # Return:
            # return land count for current land to parent land 
            # (and eventually return to the original root land we hit)
            return area
    
        # iterate over all cells
        # tc: O(r*c)
        for r in range(m):
            for c in range(n):

                # Initial Call:
                # land that has not been visited found, start dfs exploration at cell
                # tc: O(1)
                if grid[r][c] == 1:

                    # found new island, get island area
                    island_area = dfs_SinkVisitedIsland(r, c)

                    # compare local island area to global max island area
                    max_area = max(max_area, island_area)

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

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        
        # Note:
        # 1. Treat grid as a graph: 1 = land, edges = 4-direction adjacency
        # 2. BFS explores each island iteratively using a queue
        # 3. Sink land cells in-place to mark visited
        # 4. Track area of each island, return maximum

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

        # sc: setting up search space rows [0, n-1] and columns [0 n-1] O(1)
        m, n = len(grid), len(grid[0])

        # Tracking Global Max Island
        # sc: O(1)
        max_area = 0


        def bfs_SinkVisitedLand(r, c):

            # area count for local island
            area = 0

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

            # Add root land to queue execution
            queue.append((r, c))

            # Build:
            # Sink root island
            grid[r][c] = 0  # mark visited

            # While we have land in current island
            while queue:

                # Get Bottom Of Queue Cell (original root):
                # tc O(1)
                cr, cc = queue.popleft()

                # Add to local island land counter
                area += 1

                # Explore:
                # iteratively visit all neighbors (up, down, left, right)
                # tc: O(1) per call, but overall bounded by number of cells
                # sc: O(r*c) recursion stack grows with connected component size
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = cr + dr, cc + dc

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

                        # Process Root:
                        # mark current cell as visited
                        # tc: O(1), sc: O(1)
                        grid[nr][nc] = 0

                        # Add land to bfs queue for execution
                        queue.append((nr, nc))

            # Return:
            # pass local island area to root island
            return area


        # iterate over all cells
        # tc: O(r*c)
        for r in range(m):
            for c in range(n):

                # Initial Call:
                # land that has not been visited found, start bfs exploration at cell
                # tc: O(1)
                if grid[r][c] == 1:

                    # found new island
                    island_area = bfs_SinkVisitedLand(r, c)

                    # compare local island area to global island area
                    max_area = max(max_area, island_area)


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

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        # Note:
        # Union-Find approach to track connected components by size
        # 1. Process Root -> initialize parent and size for each land cell
        # 2. Process Candidates -> union adjacent land cells (down/right)
        # 3. Early Prune -> skip out-of-bounds
        # 4. Late Prune -> skip water cells
        # Result: max size among all connected components = max island area

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

        # sc: setting up search space rows [0, n-1] and columns [0 n-1] O(1)
        m, n = len(grid), len(grid[0])

        # Parent and size for each land cell
        # sc: O(r*c) 
        parent = {}
        size = {}

        # Initialize Union Find:
        # tc: iterate over all cells O(r*c)
        # sc: add all cells O(r*c)
        for r in range(m):
            for c in range(n):
                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):

            # if parent of cell isn't self, go up to parent
            if parent[x] != x:
                parent[x] = find(parent[x])

            # returns parent of original, after path compression
            return parent[x]

        # Union by Rank
        # tc: O(α(n)) amortized
        # sc: O(1)
        def union(x, y):
            
            # Ignore if nodes share the same root (part of the same island)
            # This will act as:
            #   - tracking visited nodes: marks all land in a island
            #   - will not connect land already marked as being in the same island
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return
            
            # Union By Rank (upper bound on tree height)
            # tc: O(1)
            if size[rootX] >= size[rootY]:
                parent[rootY] = rootX
                size[rootX] += size[rootY]
            else:
                parent[rootX] = rootY
                size[rootY] += size[rootX]


        # iterate over all cells
        # tc: O(r*c)
        for r in range(m):
            for c in range(n):

                # Initial Call:
                # land has been found, start dfs exploration at cell
                # tc: O(1), sc: O(1)
                if grid[r][c] == 1:

                    # Explore:
                    # Union the adjacent lands, 
                    # only down and right as we will finish the rest 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))

        # Return tree with most nodes
        largestIsland = max(size.values(), default=0)

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

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        
        # Note:
        # 1. Use DFS to traverse the graph
        # 2. Use a hashmap to store already cloned nodes
        # 3. For each node, recursively clone its neighbors
        # 4. Return the cloned node corresponding to the input
        
        # Empty Check: no islands, grid is empty
        # tc: O(1)
        if not node:
            return None

        # Deep copy for new list
        # sc: O(n)
        cloned = {}

        # tc O(V + E) visit each node and edge once
        # sc O(V), for hashmap + recursion stack
        def dfs(n) -> Node:

            # Process Root:
            # clone current node
            copy = Node(n.val)

            # Add clone to hashmap
            cloned[n] = copy

            # Process Candidates:
            # recursively clone all neighbors
            for neighbor in n.neighbors:
                
                # Early Prune: only recurse if neighbor not yet cloned
                if neighbor not in cloned:
                    copy.neighbors.append(dfs(neighbor))
                # else just grab neighbor from clone hashmap
                else:
                    copy.neighbors.append(cloned[neighbor])

            # Return:
            # pass back the cloned node
            return copy

        # Initial Call:
        # return new root of cloned graph
        cloneRoot = dfs(node)

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

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        
        # Note:
        # 1. Iterative BFS traversal to clone graph nodes
        # 2. Use hashmap to track original -> cloned node
        # 3. Process Root -> start with input node in queue
        # 4. Process Candidates -> clone neighbors iteratively
        # 5. Early Prune -> skip already cloned neighbors
        # 6. Backtrack -> queue ensures all reachable nodes are processed

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

        # Deep copy of root for new list
        # sc: O(n)
        cloned = {node: Node(node.val)}

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

        # Append Original Root Node
        # tc: O(1)
        queue.append(node)

        # While we still have nodes in original graph
        # tc O(V + E), each node and edge visited once
        # sc O(V), for hashmap + queue
        while queue:

            # Get Bottom Of Queue Node (original root):
            # tc O(1)
            current = queue.popleft()

            # Iterate over node's neighbors
            for neighbor in current.neighbors:

                # Early Prune: only recurse if neighbor not yet cloned
                if neighbor not in cloned:
                    cloned[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)

                # Grab neighbor from clone hashmap
                cloned[current].neighbors.append(cloned[neighbor])

        cloneRoot = cloned[node]

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

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # 1. Instead of simulating water flow forward (downhill), reverse the process,
        #    start from the oceans and "climb uphill" to neighbors with height >= current.
        # 2. DFS is used for traversal; recursion handles the exploration
        # 3. Each ocean has its own visited set
        # 4. Cells visited in both traversals can reach both oceans
        # 5. Intersection of visited sets gives the answer


        # Empty check
        if not heights:
            return []

        # boundaries
        m, n = len(heights), len(heights[0])

        # seen
        pacific = set()
        atlantic = set()


        def dfs_TravelUphill(r: int, c: int, ocean_visited: set, prev_height: int) -> None:
            
            # Late Prune:
            # ignore cells if they are out of bounds or visited
            # but specifically if they are downhill, as this means they cannot reach the island
            if (r < 0 or r >= m or 
                c < 0 or c >= n or
                (r, c) in ocean_visited or 
                heights[r][c] < prev_height):
                return

            # Process Root:
            # mark cell as ocean_visited
            ocean_visited.add((r, c))

            # Process Candidates:
            # recursively explore neighbors explore 4 directions
            dfs_TravelUphill(r + 1, c, ocean_visited, heights[r][c])
            dfs_TravelUphill(r - 1, c, ocean_visited, heights[r][c])
            dfs_TravelUphill(r, c + 1, ocean_visited, heights[r][c])
            dfs_TravelUphill(r, c - 1, ocean_visited, heights[r][c])

        # Process Roots:
        # start from Pacific and Atlantic edges
        # These are the edge cells adjacent to each ocean from which water can "flow uphill"
        # just collecting outermost edge calls

        for i in range(m):
            # left column
            dfs_TravelUphill(i, 0, pacific, heights[i][0])
            # right column
            dfs_TravelUphill(i, n - 1, atlantic, heights[i][n - 1])
        for j in range(n):
            # top row
            dfs_TravelUphill(0, j, pacific, heights[0][j])
            # bottom row
            dfs_TravelUphill(m - 1, j, atlantic, heights[m - 1][j])

        # Cells reachable to both oceans
        # tc: O(V)
        intersection = list(pacific & atlantic)

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

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # 1. Same reverse flow idea, but BFS is used instead of DFS.
        # 2. BFS avoids recursion depth issues and may be easier to reason about.
        # 3. Initialize queues with Pacific and Atlantic edges separately.
        # 4. Traverse "uphill" from oceans, track visited cells for each.
        # 5. Answer = intersection of both visited sets.

        # Empty check
        if not heights:
            return []

        # boundaries
        m, n = len(heights), len(heights[0])

        # 
        def bfs(starts: List[Tuple[int,int]]) -> set:

            # Visited set for BFS traversal
            ocean_visited = set(starts)

            # Iterative queue
            queue = deque(starts)

            while queue:
                # Process Root:
                # Grab leftmost cell
                r, c = queue.popleft()

                # Process Choices:
                # Recursively explore neighbors
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = r + dr, c + dc

                    # Early Prune:
                    # skip if cell is out of bounds or visited
                    # but most importantly uphill as that means
                    if (0 <= nr < m and 
                        0 <= nc < n and 
                        (nr, nc) not in ocean_visited and 
                        heights[nr][nc] >= heights[r][c]):

                        # mark as visited
                        ocean_visited.add((nr, nc))

                        # add neighbor for processing
                        queue.append((nr, nc))
                        
            # Return all visited cells for this ocean
            return ocean_visited

        # Process Roots -> edge cells for each ocean
        # These are the edge cells adjacent to each ocean from which water can "flow uphill"
        # just collecting outermost edge calls

        # pacific_starts = all cells on the top row (0, j) and all cells on the left column (i, 0)
        pacific_starts = []

        # Top row (first row) for Pacific
        for j in range(n):
            pacific_starts.append((0, j))

        # Left column (first column) for Pacific
        for i in range(m):
            pacific_starts.append((i, 0))

        # Atlantic Ocean edge cells
        atlantic_starts = []

        # Bottom row (last row) for Atlantic
        for j in range(n):
            atlantic_starts.append((m - 1, j))

        # Right column (last column) for Atlantic
        for i in range(m):
            atlantic_starts.append((i, n - 1))

        pacific = bfs(pacific_starts)
        atlantic = bfs(atlantic_starts)

        # Cells reachable to both oceans
        # tc: O(V)
        intersection = list(pacific & atlantic)

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

    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 openLock(self, deadends: List[str], target: str) -> int:
        
        # Convert deadends to a set for O(1) lookup
        dead = set(deadends)
        
        # Edge Case:
        # If starting position is a deadend,
        # we cannot move.
        if "0000" in dead:
            return -1
        
        # Standard BFS setup
        queue = deque([("0000", 0)])  # (state, moves)
        visited = set(["0000"])
        
        while queue:
            state, moves = queue.popleft()
            
            # If target reached
            if state == target:
                return moves
            
            # Generate all possible next states
            for i in range(4):
                
                digit = int(state[i])
                
                # Two possible rotations:
                # +1 and -1 (with wraparound)
                for change in (-1, 1):
                    
                    new_digit = (digit + change) % 10
                    
                    # Build new state string
                    new_state = (
                        state[:i] +
                        str(new_digit) +
                        state[i+1:]
                    )
                    
                    # Only proceed if:
                    # - not visited
                    # - not a deadend
                    if new_state not in visited and new_state not in dead:
                        
                        visited.add(new_state)
                        queue.append((new_state, moves + 1))
        
        # If BFS exhausts without finding target
        return -1

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        
        # 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:

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

        # Union-Find Approach:
        # Instead of traversing each component like DFS/BFS,
        # we "union" nodes as we process edges.
        # Two nodes sharing the same root are in the same component.

        # 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 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)