def multi_source_bfs(graph, sources):

        visited = set(sources)
        distance = {node: 0 for node in sources}  # Distance from nearest source
        queue = deque(sources)

        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    distance[neighbor] = distance[node] + 1
                    queue.append(neighbor)

        return distance

    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        # Multi Source BFS (Time Stored In Queue)
        # Determine minimum minutes required for all fresh oranges to rot

        # Idea:
        # - Start BFS from ALL rotten oranges simultaneously
        # - Each expansion spreads rot to neighbors
        # - Time (minutes) is carried inside queue state

        # BFS Property:
        # First time an orange is visited = earliest minute it rots

        # Edge Case + Setup

        # Empty Check: no time
        if not grid:
            return -1

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

        # Count Fresh Oranges
        fresh = 0

        # Final Elapsed Time
        minutes = 0

        # Iterative Queue Holds: (row, col, minute)
        # sc: O(m*n)
        queue = deque()

        # Multi Source Setup:
        #   - get total count of fresh oranges
        #   - put all rotten oranges in BFS queue
        # tc: O(m*n)
        for r in range(m):
            for c in range(n):

                # Append rotten oranges to iterative bfs queue
                if grid[r][c] == 2:
                    # add rotten orange as (row, col, minute)
                    queue.append((r, c, 0))
                
                # Add to fresh count
                elif grid[r][c] == 1:
                    fresh += 1

        # BFS Traversal:
        # Each poop represents earliest time this cell rots
        # tc: O(m*n) each cell processed once
        while queue:

            # Process Root
            r, c, minutes = queue.popleft()

            # Process Choices:
            # 4 direction spread
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc

                # Early Prune:
                # valid bounds + fresh orange
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:

                    # Rot orange immediately
                    grid[nr][nc] = 2
                    fresh -= 1
                    
                    # Pass next minute down BFS
                    queue.append((nr, nc, minutes + 1))

        # Final Validation:
        # if fresh oranges remain, they are unreachable
        res = minutes if fresh == 0 else -1

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

    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        # Multi Source BFS (Time Stored In Queue)
        # Determine minimum minutes required for all fresh oranges to rot

        # Idea:
        # - Start BFS from ALL rotten oranges simultaneously
        # - Each expansion spreads rot to neighbors
        # - Time (minutes) is carried inside queue state

        # BFS Property:
        # First time an orange is visited = earliest minute it rots

        # Edge Case + Setup

        # Empty Check: no time
        if not grid:
            return -1

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

        # Count Fresh Oranges
        fresh = 0

        # Final Elapsed Time
        minutes = 0

        # Iterative Queue Holds: (row, col, minute)
        # sc: O(m*n)
        queue = deque()

        # Multi Source Setup
        # Iterate across all cells
        # tc: O(m*n)
        for r in range(m):
            for c in range(n):

                # Append ALL rotten oranges as BFS roots
                if grid[r][c] == 2:
                    # add rotten orange as (row, col, minute)
                    queue.append((r, c, 0))
                
                # Add to fresh count
                elif grid[r][c] == 1:
                    fresh += 1

        # BFS Traversal:
        # Each poop represents earliest time this cell rots
        # tc: O(m*n) each cell processed once
        while queue and fresh > 0:

            # Process Multiple Roots:
            # All sources at this level
            for _ in range(len(queue)):

                # Process current root
                r, c = queue.popleft()

                # Process Choices:
                # 4 direction spread
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = r + dr, c + dc

                    # Early Pruning:
                    # Valid bounds and fresh fruit
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:

                        # Rot orange immediately
                        grid[nr][nc] = 2
                        fresh -= 1

                        # Add next rotten source to queue
                        queue.append((nr, nc))

            # Iterate global minutes tick for next source level
            minutes += 1

        # Final Validation:
        # if fresh oranges remain, they are unreachable
        res = minutes if fresh == 0 else -1

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

    def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        if not grid:
            return

        m, n = len(grid), len(grid[0])
        INF = 2147483647
        q = deque()

        # Step 1: Collect all treasure chests (multi-source roots)
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 0:
                    q.append((r, c))

        # Step 2: BFS flood fill
        while q:
            r, c = q.popleft()

            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc

                # Late Candidate Prune: out of bounds or not INF
                if not (0 <= nr < m and 0 <= nc < n):
                    continue
                if grid[nr][nc] != INF:
                    continue

                # Process Root: update distance from nearest treasure
                grid[nr][nc] = grid[r][c] + 1

                # Process Choices: explore neighbor
                q.append((nr, nc))

        # overall: time O(m * n), space O(m * n) (queue worst-case)

    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:

        # Note:
        # Multi-source BFS: instead of starting from ONE source, seed the queue
        # with ALL water cells simultaneously (height 0), then expand outward together
        # 1. Process all water cells -> :
        #    height 0, added to queue as starting frontier
        # 2. Process -> neighbors :
        #    each unvisited neighbor is exactly 1 higher than the cell that reached it first
        # Result: BFS guarantees the FIRST time a cell is reached is via the
        #         SHORTEST path from its nearest water cell -> correct height

        # Dimensions
        m, n = len(isWater), len(isWater[0])

        # height: -1 sentinel means unvisited; water cells get 0, land gets filled in via BFS
        # sc: O(m*n)
        height = [[-1] * n for _ in range(m)]

        # queue: multi-source BFS frontier, seeded with ALL water cells at once
        queue = deque()

        # Seed queue:
        # every water cell starts as height 0, source of its own BFS wave
        for r in range(m):
            for c in range(n):
                if isWater[r][c] == 1:
                    height[r][c] = 0
                    queue.append((r, c))

        # directions: up, down, left, right (4-directional grid movement)
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # BFS: propagate heights outward level by level from all water cells
        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Early pruning:
                # skip out-of-bounds or already-visited cells
                # (already-visited means a closer water source already claimed it)
                if 0 <= nr < m and 0 <= nc < n and height[nr][nc] == -1:
                    height[nr][nc] = height[r][c] + 1
                    queue.append((nr, nc))

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

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

        # Idea:
        #    two islands exist in the grid, connected only through water (0s)
        #    step 1: DFS from any land cell finds and marks the entire first
        #    island (flip its cells to 2), seeding a queue with every cell
        #    of that island along the way
        #    step 2: multi-source BFS expands outward from the whole first
        #    island simultaneously, one water ring per level — the first
        #    time a cell adjacent to unflipped land (1) is reached, that
        #    ring count is the minimum number of water cells crossed

        n = len(grid)

        # directions: the 4 neighbor offsets to check per cell (up, down, left, right)
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(x, y, q):

            # Check:
            # mark this land cell as visited/part of the first island,
            # and seed it into the BFS queue as one of many starting points
            grid[x][y] = 2
            q.append((x, y))

            # Check:
            # explore all 4 neighbors, descending into any unvisited land
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                    dfs(nx, ny, q)

        # BFS Multi-Source Queue:
        # every cell belonging to the first island gets added here via DFS,
        # BEFORE the BFS loop below ever starts. This is what makes the next
        # phase multi-source: all of these cells enter the BFS already
        # sitting in the queue together, all treated as distance 0 at once —
        # not as separate single-source runs processed one at a time.
        queue = deque()

        # Check:
        # scan the grid for the first land cell found, DFS from there to
        # mark the entire first island — problem guarantees exactly two
        # islands, so any land cell belongs to one of them
        found = False
        for i in range(n):
            if found:
                break
            for j in range(n):
                if grid[i][j] == 1:
                    dfs(i, j, queue)
                    found = True
                    break

        # Check:
        # multi-source BFS: the queue already holds every cell of the first
        # island as simultaneous starting points. Each pass through the
        # `for _ in range(len(queue))` loop processes one entire frontier —
        # every cell currently in the queue, regardless of which original
        # island-1 cell it traces back to — before `steps` increments.
        # This guarantees the ring that first touches the second island is
        # the globally shortest distance from ANY point on the first island,
        # not just the distance from one arbitrarily chosen source.
        steps = 0
        while queue:
            for _ in range(len(queue)):
                x, y = queue.popleft()

                # Check:
                # examine all 4 neighbors of this cell
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n:

                        # Check:
                        # neighbor is unflipped land — this is the second
                        # island, shortest bridge found
                        if grid[nx][ny] == 1:
                            return steps

                        # Check:
                        # neighbor is unvisited water, mark visited and
                        # enqueue it to expand this shared frontier further
                        elif grid[nx][ny] == 0:
                            grid[nx][ny] = 2
                            queue.append((nx, ny))
            steps += 1

        # Check:
        # unreachable in practice — problem guarantees exactly two islands,
        # so the second island is always found during the BFS expansion
        
        # overall: tc O(n^2)
        # overall: sc O(n^2)
        return -1

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # 1. Instead of simulating water flow downhill, 
        #    we reverse the process and  start from the ocean cells 
        #    and climb uphill to neighbors with height larger than the current cell,
        #    as when reversing ensures flow downhill.
        # 2. Each ocean will have its own visited set,
        #    which are cells that the ocean can reach while climbing upwards,
        #    or vice versa cells that can reach the ocean while flowing downwards.
        # 3. Cells that end up in both ocean sets can reach both oceans
        #    while flowing downhill


        # Empty check:
        if not heights:
            return []

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

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


        def dfs(r, c, oceanVisited, prev_height) -> None:
            
            # Check:
            # mark this cell as reachable from the ocean
            oceanVisited.add((r, c))

            # Check Neighbors:
            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                
                # Valid Neighbor:
                #   - in bounds
                #   - not yet visited
                #   - height is taller or equal than current cell
                if (0 <= nr < m and 0 <= nc < n and
                        (nr, nc) not in ocean_visited and
                        heights[nr][nc] >= heights[r][c]):
                    
                    # Explore Neighbor:
                    dfs(nr, nc, oceanVisited, heights[r][c])

        # Explore Pacific and Atlantic Edges:
        for i in range(m):
            # left column
            dfs(i, 0, pacific, heights[i][0])
            # right column
            dfs(i, n - 1, atlantic, heights[i][n - 1])
        for j in range(n):
            # top row
            dfs(0, j, pacific, heights[0][j])
            # bottom row
            dfs(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 []

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


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

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

            # Iterative BFS queue
            queue = deque(starts)

            while queue:

                # Pop land cell
                r, c = queue.popleft()

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

                    # New land cell
                    nr, nc = r + dr, c + dc

                    # Early Prune:
                    #   - if cell is out of bounds or visited
                    #   - if cell is uphill
                    if (0 <= nr < m and 0 <= nc < n and 
                        (nr, nc) not in oceanVisited and 
                        heights[nr][nc] >= heights[r][c]):

                        # Mark as visited, which means reachable via just uphill 
                        # from ocean -> land cell
                        oceanVisited.add((nr, nc))
                        queue.append((nr, nc))
                        
            # Return all visited cells for this ocean
            # tc: O(n)
            # sc: O(n)
            return oceanVisited



        # Explore Pacific and Atlantic Edges:


        # Pacific:
        #   - Top row (first row)
        #   - Left column (first column)
        pacificOceanCells = []
        for j in range(n):
            pacificOceanCells.append((0, j))
        for i in range(m):
            pacificOceanCells.append((i, 0))

        # Atlantic:
        #   - Bottom row (last row)
        #   - Right column (last column)
        atlanticOceanCells = []
        for j in range(n):
            atlantic_starts.append((m - 1, j))
        for i in range(m):
            atlantic_starts.append((i, n - 1))

        # Reachable land cells for both pacific and atlantic
        pacific = bfs(pacificOceanCells)
        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