from collections import deque
from typing import List

def multi_source_bfs(grid: List[List[int]], is_source, is_valid_target) -> int:
    """
    Multi-source BFS template for grid problems.

    Core invariant:
    - All sources start at distance 0 (initialized in queue simultaneously)
    - BFS guarantees shortest distance property
    - Each cell is visited exactly once

    Args:
        grid: The 2D grid
        is_source: Function to identify source cells
        is_valid_target: Function to identify cells that can be reached/modified

    Returns:
        Maximum distance reached (or -1 if targets remain unreached)
    """
    if not grid or not grid[0]:
        return 0

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

    # Phase 1: Initialize - collect all sources at distance 0
    target_count = 0
    for r in range(rows):
        for c in range(cols):
            if is_source(grid[r][c]):
                queue.append((r, c))
            elif is_valid_target(grid[r][c]):
                target_count += 1

    # Early termination: no targets to process
    if target_count == 0:
        return 0

    # Phase 2: BFS expansion
    DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    distance = 0

    while queue:
        # Process all cells at current distance level
        for _ in range(len(queue)):
            r, c = queue.popleft()

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

                # Boundary check and valid target check
                if 0 <= nr < rows and 0 <= nc < cols:
                    if is_valid_target(grid[nr][nc]):
                        # Mark as visited (convert to source state)
                        grid[nr][nc] = grid[r][c]  # Or mark with distance
                        queue.append((nr, nc))
                        target_count -= 1

        distance += 1

    # Phase 3: Return result based on problem type
    return distance - 1 if target_count == 0 else -1

# 4-directional movement (standard for most grid BFS)
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def in_bounds(r: int, c: int, rows: int, cols: int) -> bool:
    """Check if coordinates are within grid boundaries."""
    return 0 <= r < rows and 0 <= c < cols

def get_neighbors(r: int, c: int, rows: int, cols: int):
    """Generate valid 4-directional neighbors."""
    for dr, dc in DIRECTIONS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0

        # Phase 1: Initialize sources and count targets
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:      # Source: rotten orange
                    queue.append((r, c))
                elif grid[r][c] == 1:    # Target: fresh orange
                    fresh_count += 1

        # Early exit: no fresh oranges
        if fresh_count == 0:
            return 0

        # Phase 2: Multi-source BFS expansion
        DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        minutes = 0

        while queue:
            # Process entire current level
            for _ in range(len(queue)):
                r, c = queue.popleft()

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

                    if 0 <= nr < rows and 0 <= nc < cols:
                        if grid[nr][nc] == 1:  # Fresh orange found
                            grid[nr][nc] = 2   # Mark as rotten (visited)
                            queue.append((nr, nc))
                            fresh_count -= 1

            minutes += 1

        # Phase 3: Check if all targets reached
        # Subtract 1 because we count one extra level after last infection
        return minutes - 1 if fresh_count == 0 else -1

from collections import deque
from typing import List

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Modify rooms in-place to store distance to nearest gate.
        """
        if not rooms or not rooms[0]:
            return

        INF = 2147483647
        rows, cols = len(rooms), len(rooms[0])
        queue = deque()

        # Phase 1: Initialize - all gates are sources at distance 0
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:  # Gate found
                    queue.append((r, c))

        # Phase 2: BFS from all gates simultaneously
        DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while queue:
            r, c = queue.popleft()

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

                if 0 <= nr < rows and 0 <= nc < cols:
                    # Only process empty rooms (INF)
                    # Rooms already filled have shorter distance
                    if rooms[nr][nc] == INF:
                        rooms[nr][nc] = rooms[r][c] + 1
                        queue.append((nr, nc))

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        queue = deque()

        # Phase 1: Initialize distance matrix
        # Zeros have distance 0, ones start with infinity
        dist = [[0 if mat[r][c] == 0 else float('inf')
                 for c in range(cols)] for r in range(rows)]

        # Add all zeros to queue (sources at distance 0)
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    queue.append((r, c))

        # Phase 2: BFS from all zeros
        DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while queue:
            r, c = queue.popleft()

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

                if 0 <= nr < rows and 0 <= nc < cols:
                    # Update if we found a shorter path
                    new_dist = dist[r][c] + 1
                    if new_dist < dist[nr][nc]:
                        dist[nr][nc] = new_dist
                        queue.append((nr, nc))

        return dist

class SolutionInPlace:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        """
        Modify matrix in-place using -1 as 'unvisited one' marker.
        """
        rows, cols = len(mat), len(mat[0])
        queue = deque()

        # Mark all ones as unvisited (-1), add zeros to queue
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    queue.append((r, c))
                else:
                    mat[r][c] = -1  # Unvisited marker

        DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        distance = 0

        while queue:
            distance += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()

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

                    if 0 <= nr < rows and 0 <= nc < cols:
                        if mat[nr][nc] == -1:  # Unvisited one
                            mat[nr][nc] = distance
                            queue.append((nr, nc))

        return mat

# DP approach (for reference):
# Pass 1: top-left to bottom-right (check top and left)
# Pass 2: bottom-right to top-left (check bottom and right)

# ===== Rotting Oranges =====
# Sources: grid[r][c] == 2
# Targets: grid[r][c] == 1
# Update:  grid[nr][nc] = 2
# Result:  minutes - 1 if fresh == 0 else -1

# ===== Walls and Gates =====
# Sources: rooms[r][c] == 0
# Targets: rooms[r][c] == INF
# Update:  rooms[nr][nc] = rooms[r][c] + 1
# Result:  in-place modification (void)

# ===== 01 Matrix =====
# Sources: mat[r][c] == 0
# Targets: mat[r][c] == 1 (or dist[r][c] == inf)
# Update:  dist[nr][nc] = dist[r][c] + 1
# Result:  distance matrix

from collections import deque
from typing import List

def propagation_timer(grid: List[List[int]], SOURCE: int, TARGET: int) -> int:
    """
    Count levels until all targets are converted to sources.

    Returns: number of levels (time units), or -1 if impossible
    Use for: LC 994 (Rotting Oranges)
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    queue = deque()
    target_count = 0

    # Initialize: collect sources, count targets
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == SOURCE:
                queue.append((r, c))
            elif grid[r][c] == TARGET:
                target_count += 1

    if target_count == 0:
        return 0

    DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    levels = 0

    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in DIRECTIONS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if grid[nr][nc] == TARGET:
                        grid[nr][nc] = SOURCE
                        queue.append((nr, nc))
                        target_count -= 1
        levels += 1

    return levels - 1 if target_count == 0 else -1

from collections import deque
from typing import List

def distance_fill(grid: List[List[int]], SOURCE: int, INF: int) -> None:
    """
    Fill each INF cell with distance to nearest SOURCE.
    Modifies grid in-place.

    Use for: LC 286 (Walls and Gates)
    """
    if not grid or not grid[0]:
        return

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

    # Initialize: all sources at distance 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == SOURCE:
                queue.append((r, c))

    DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRECTIONS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == INF:
                    grid[nr][nc] = grid[r][c] + 1
                    queue.append((nr, nc))

from collections import deque
from typing import List

def distance_matrix(mat: List[List[int]], SOURCE_VAL: int = 0) -> List[List[int]]:
    """
    Return new matrix where each cell contains distance to nearest source.

    Use for: LC 542 (01 Matrix)
    """
    rows, cols = len(mat), len(mat[0])
    queue = deque()

    # Initialize distance matrix
    dist = [[0 if mat[r][c] == SOURCE_VAL else float('inf')
             for c in range(cols)] for r in range(rows)]

    # Add all sources
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == SOURCE_VAL:
                queue.append((r, c))

    DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRECTIONS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                new_dist = dist[r][c] + 1
                if new_dist < dist[nr][nc]:
                    dist[nr][nc] = new_dist
                    queue.append((nr, nc))

    return dist

from collections import deque
from typing import List, Callable

def multi_source_bfs_generic(
    grid: List[List[int]],
    is_source: Callable[[int], bool],
    is_target: Callable[[int], bool],
    mark_visited: Callable[[List[List[int]], int, int, int], None],
    directions: List[tuple] = None
) -> int:
    """
    Generic multi-source BFS with customizable predicates.

    Args:
        is_source: lambda cell_value -> bool
        is_target: lambda cell_value -> bool
        mark_visited: function(grid, r, c, dist) to mark cell as visited

    Returns: max distance reached
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    queue = deque()
    directions = directions or [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Initialize
    for r in range(rows):
        for c in range(cols):
            if is_source(grid[r][c]):
                queue.append((r, c, 0))

    max_dist = 0

    while queue:
        r, c, dist = queue.popleft()
        max_dist = max(max_dist, dist)

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if is_target(grid[nr][nc]):
                    mark_visited(grid, nr, nc, dist + 1)
                    queue.append((nr, nc, dist + 1))

    return max_dist