# Adjacency List (most common for sparse graphs)
graph: dict[int, list[int]] = {
    0: [1, 2],      # Node 0 connects to nodes 1 and 2
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# Edge List
edges: list[tuple[int, int]] = [(0, 1), (0, 2), (1, 3), (2, 3)]

# Adjacency Matrix (dense graphs)
matrix: list[list[int]] = [
    [0, 1, 1, 0],   # Node 0's connections
    [1, 0, 0, 1],   # Node 1's connections
    [1, 0, 0, 1],   # Node 2's connections
    [0, 1, 1, 0]    # Node 3's connections
]

# Grid as implicit graph
grid: list[list[int]] = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
# Neighbors: (row±1, col±1) for 4-directional, add diagonals for 8-directional

def dfs(node: int, graph: dict, visited: set) -> None:
    """
    DFS template using recursion.

    Core invariant:
    - visited set prevents revisiting nodes
    - Process node BEFORE recursing (preorder) or AFTER (postorder)
    """
    if node in visited:
        return

    visited.add(node)

    # Process current node (preorder position)

    for neighbor in graph[node]:
        dfs(neighbor, graph, visited)

    # Process current node (postorder position)

from collections import deque

def bfs(start: int, graph: dict) -> None:
    """
    BFS template using queue.

    Core invariant:
    - Nodes at distance d are processed before nodes at distance d+1
    - visited set prevents revisiting and infinite loops
    """
    visited: set[int] = {start}
    queue: deque[int] = deque([start])

    while queue:
        node = queue.popleft()

        # Process current node

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)  # Mark visited BEFORE adding to queue
                queue.append(neighbor)

# 4-directional movement
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def get_neighbors(row: int, col: int, rows: int, cols: int) -> list[tuple[int, int]]:
    """Get valid 4-directional neighbors."""
    neighbors = []
    for dr, dc in DIRECTIONS:
        nr, nc = row + dr, col + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            neighbors.append((nr, nc))
    return neighbors

# 8-directional movement (includes diagonals)
DIRECTIONS_8 = [(0, 1), (0, -1), (1, 0), (-1, 0),
                (1, 1), (1, -1), (-1, 1), (-1, -1)]

# Pattern: graph_dfs_connected_components
# See: docs/patterns/graph/templates.md Section 1 (Base Template)

class SolutionDFS:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
        Count islands using DFS to mark connected land cells.

        Key Insight:
        - Each unvisited '1' starts a new island
        - DFS from that cell marks all connected '1's as visited
        - Number of DFS calls = number of islands

        Why mark in-place?
        - Change '1' to '0' to mark as visited
        - Avoids separate visited set (saves space)
        - Alternatively, use visited set if grid shouldn't be modified
        """
        if not grid or not grid[0]:
            return 0

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

        def dfs(row: int, col: int) -> None:
            """Flood fill: mark all connected land cells."""
            # Boundary check and water/visited check
            if (row < 0 or row >= rows or
                col < 0 or col >= cols or
                grid[row][col] != '1'):
                return

            # Mark as visited (sink the land)
            grid[row][col] = '0'

            # Explore 4 directions
            dfs(row + 1, col)  # Down
            dfs(row - 1, col)  # Up
            dfs(row, col + 1)  # Right
            dfs(row, col - 1)  # Left

        # Main loop: find and count islands
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == '1':
                    island_count += 1
                    dfs(row, col)  # Mark entire island as visited

        return island_count

from collections import deque

class SolutionBFS:
    def numIslands(self, grid: List[List[str]]) -> int:
        """BFS approach - iterative, uses explicit queue."""
        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])
        island_count = 0
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def bfs(start_row: int, start_col: int) -> None:
            queue = deque([(start_row, start_col)])
            grid[start_row][start_col] = '0'

            while queue:
                row, col = queue.popleft()
                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < rows and 0 <= nc < cols and
                        grid[nr][nc] == '1'):
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == '1':
                    island_count += 1
                    bfs(row, col)

        return island_count

# Pattern: graph_clone
# See: docs/patterns/graph/templates.md Section 2

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors else []

class SolutionDFS:
    def cloneGraph(self, node: 'Node') -> 'Node':
        """
        Clone graph using DFS with hash map for node mapping.

        Key Insight:
        - Map: original node → cloned node
        - On first visit: create clone and add to map
        - On subsequent visits: return existing clone from map
        - This handles cycles: when we see a visited node, we use its clone

        Why hash map?
        - Detect already-cloned nodes (handles cycles)
        - Retrieve clone when building neighbor lists
        """
        if not node:
            return None

        # Map: original node → cloned node
        old_to_new: dict[Node, Node] = {}

        def dfs(original: Node) -> Node:
            # If already cloned, return the clone
            if original in old_to_new:
                return old_to_new[original]

            # Create clone (without neighbors yet)
            clone = Node(original.val)
            old_to_new[original] = clone

            # Clone all neighbors recursively
            for neighbor in original.neighbors:
                clone.neighbors.append(dfs(neighbor))

            return clone

        return dfs(node)

from collections import deque

class SolutionBFS:
    def cloneGraph(self, node: 'Node') -> 'Node':
        """BFS approach - iterative cloning."""
        if not node:
            return None

        old_to_new: dict[Node, Node] = {node: Node(node.val)}
        queue: deque[Node] = deque([node])

        while queue:
            original = queue.popleft()

            for neighbor in original.neighbors:
                if neighbor not in old_to_new:
                    # Create clone and add to map
                    old_to_new[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)

                # Add cloned neighbor to cloned node's neighbors
                old_to_new[original].neighbors.append(old_to_new[neighbor])

        return old_to_new[node]

# Pattern: graph_bfs_multi_source
# See: docs/patterns/graph/templates.md Section 3

from collections import deque

class SolutionBFS:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        """
        Find cells that can reach both oceans using reverse BFS.

        Key Insight:
        - Forward: Check if water from cell reaches ocean (complex)
        - Reverse: Check if ocean can reach cell going UPHILL (simpler)

        Why reverse direction?
        - Ocean borders are known sources
        - Multi-source BFS finds all reachable cells efficiently
        - Intersection gives cells reaching both oceans
        """
        if not heights or not heights[0]:
            return []

        rows, cols = len(heights), len(heights[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def bfs(sources: list[tuple[int, int]]) -> set[tuple[int, int]]:
            """Multi-source BFS to find all reachable cells."""
            reachable: set[tuple[int, int]] = set(sources)
            queue: deque[tuple[int, int]] = deque(sources)

            while queue:
                row, col = queue.popleft()

                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    # Can flow uphill (from ocean's perspective)
                    if (0 <= nr < rows and 0 <= nc < cols and
                        (nr, nc) not in reachable and
                        heights[nr][nc] >= heights[row][col]):
                        reachable.add((nr, nc))
                        queue.append((nr, nc))

            return reachable

        # Pacific: top row + left column
        pacific_sources = (
            [(0, col) for col in range(cols)] +
            [(row, 0) for row in range(rows)]
        )

        # Atlantic: bottom row + right column
        atlantic_sources = (
            [(rows - 1, col) for col in range(cols)] +
            [(row, cols - 1) for row in range(rows)]
        )

        # Find cells reachable from each ocean
        pacific_reach = bfs(pacific_sources)
        atlantic_reach = bfs(atlantic_sources)

        # Return intersection
        return list(pacific_reach & atlantic_reach)

class SolutionDFS:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        """DFS approach - recursive from ocean borders."""
        if not heights:
            return []

        rows, cols = len(heights), len(heights[0])
        pacific: set[tuple[int, int]] = set()
        atlantic: set[tuple[int, int]] = set()

        def dfs(row: int, col: int, reachable: set, prev_height: int) -> None:
            if (row < 0 or row >= rows or col < 0 or col >= cols or
                (row, col) in reachable or heights[row][col] < prev_height):
                return

            reachable.add((row, col))
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                dfs(row + dr, col + dc, reachable, heights[row][col])

        # DFS from ocean borders
        for col in range(cols):
            dfs(0, col, pacific, 0)
            dfs(rows - 1, col, atlantic, 0)

        for row in range(rows):
            dfs(row, 0, pacific, 0)
            dfs(row, cols - 1, atlantic, 0)

        return list(pacific & atlantic)

# Pattern: graph_bfs_multi_source
# See: docs/patterns/graph/templates.md Section 4

from collections import deque

class SolutionBFS:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        """
        Find minimum minutes for all oranges to rot using multi-source BFS.

        Key Insight:
        - All rotten oranges spread at the same time (level = minute)
        - BFS naturally processes level by level
        - Initialize queue with ALL rotten oranges (multi-source)
        - Each BFS level = 1 minute of spreading

        Why BFS, not DFS?
        - BFS processes by "wavefront" (distance from sources)
        - Each wavefront = 1 minute
        - Time = number of wavefronts = BFS depth
        """
        if not grid or not grid[0]:
            return -1

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

        # Initialize: find all rotten oranges and count fresh
        queue: deque[tuple[int, int]] = deque()
        fresh_count = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh_count += 1

        # Edge case: no fresh oranges
        if fresh_count == 0:
            return 0

        minutes = 0

        # Multi-source BFS: process level by level
        while queue:
            minutes += 1
            level_size = len(queue)

            for _ in range(level_size):
                row, col = queue.popleft()

                for dr, dc in directions:
                    nr, nc = row + dr, col + dc

                    # Check bounds and if fresh orange
                    if (0 <= nr < rows and 0 <= nc < cols and
                        grid[nr][nc] == 1):
                        # Rot the orange
                        grid[nr][nc] = 2
                        fresh_count -= 1
                        queue.append((nr, nc))

        # Check if all oranges rotted
        return minutes - 1 if fresh_count == 0 else -1

# Case 1: Fresh orange unreachable
#   2 1 1
#   0 1 1
#   1 0 1   ← (2,0) is isolated
# Return: -1

# Case 2: No fresh oranges
#   2 2 2
#   0 2 0
# Return: 0

# Case 3: All fresh oranges adjacent to rotten
#   2 1
#   1 2
# Return: 1

# After BFS completes:
# - minutes counted from 1 (first spreading)
# - But initial state is minute 0
# - Need to subtract 1 from final count

# Alternative: Start minutes = -1, increment before processing
minutes = -1
while queue:
    minutes += 1
    # process level...

# Pattern: graph_bipartite
# See: docs/patterns/graph/templates.md Section 5

from collections import deque

class SolutionBFS:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        """
        Check if graph is bipartite using BFS coloring.

        Key Insight:
        - Bipartite = can assign 2 colors so no adjacent nodes share color
        - BFS processes level by level
        - Alternate colors at each level
        - If we try to color a node that's already colored differently → conflict

        Why BFS?
        - Natural level-by-level processing
        - Each level gets opposite color
        - Easy to detect conflicts
        """
        n = len(graph)
        # -1 = uncolored, 0 = color A, 1 = color B
        color: list[int] = [-1] * n

        def bfs(start: int) -> bool:
            """BFS coloring from start node. Returns False if conflict."""
            queue: deque[int] = deque([start])
            color[start] = 0  # Start with color 0

            while queue:
                node = queue.popleft()

                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        # Uncolored: assign opposite color
                        color[neighbor] = 1 - color[node]
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        # Same color as current node → conflict
                        return False

            return True

        # Check all components (graph may be disconnected)
        for node in range(n):
            if color[node] == -1:
                if not bfs(node):
                    return False

        return True

class SolutionDFS:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        """DFS approach - recursive coloring."""
        n = len(graph)
        color: list[int] = [-1] * n

        def dfs(node: int, c: int) -> bool:
            """Try to color node with color c. Returns False if conflict."""
            if color[node] != -1:
                return color[node] == c  # Check for conflict

            color[node] = c

            for neighbor in graph[node]:
                if not dfs(neighbor, 1 - c):
                    return False

            return True

        for node in range(n):
            if color[node] == -1:
                if not dfs(node, 0):
                    return False

        return True

# Graph may have multiple components
# Example: graph = [[1], [0], [3], [2]]
#   0 -- 1    2 -- 3
#
# Must check EACH component separately
# Only need to start BFS/DFS from uncolored nodes

for node in range(n):
    if color[node] == -1:  # New component
        if not bfs(node):
            return False

# Pattern: graph_dfs_reachability
# See: docs/patterns/graph/templates.md Section 1

class SolutionDFS:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        """
        Check if all rooms are reachable from room 0 using DFS.

        Key Insight:
        - rooms[i] = list of keys in room i
        - Key to room j = directed edge i → j
        - Question: Can we reach all nodes from node 0?

        This is a standard reachability problem:
        - DFS/BFS from start node
        - Track visited nodes
        - Check if all nodes visited
        """
        n = len(rooms)
        visited: set[int] = set()

        def dfs(room: int) -> None:
            if room in visited:
                return

            visited.add(room)

            # Each key in current room leads to another room
            for key in rooms[room]:
                dfs(key)

        # Start from room 0 (always unlocked)
        dfs(0)

        # Check if all rooms visited
        return len(visited) == n

from collections import deque

class SolutionBFS:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        """BFS approach - iterative traversal."""
        n = len(rooms)
        visited: set[int] = {0}
        queue: deque[int] = deque([0])

        while queue:
            room = queue.popleft()

            for key in rooms[room]:
                if key not in visited:
                    visited.add(key)
                    queue.append(key)

        return len(visited) == n

class SolutionIterativeDFS:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        """Iterative DFS using explicit stack."""
        n = len(rooms)
        visited: set[int] = {0}
        stack: list[int] = [0]

        while stack:
            room = stack.pop()

            for key in rooms[room]:
                if key not in visited:
                    visited.add(key)
                    stack.append(key)

        return len(visited) == n

# Pattern: graph_dfs_reachability
# See: docs/patterns/graph/templates.md Section 1

from collections import defaultdict

class SolutionDFS:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        """
        Check if path exists from source to destination using DFS.

        Key Insight:
        - Build adjacency list from edge list
        - DFS from source
        - Return True if we reach destination

        Early termination: Stop as soon as destination is found.
        """
        if source == destination:
            return True

        # Build adjacency list
        graph: dict[int, list[int]] = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)  # Undirected

        visited: set[int] = set()

        def dfs(node: int) -> bool:
            if node == destination:
                return True

            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True

            return False

        return dfs(source)

from collections import deque, defaultdict

class SolutionBFS:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        """BFS approach with early termination."""
        if source == destination:
            return True

        graph: dict[int, list[int]] = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited: set[int] = {source}
        queue: deque[int] = deque([source])

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if neighbor == destination:
                    return True
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        return False

class SolutionUnionFind:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        """
        Union-Find approach - check if source and destination are in same component.

        When to use Union-Find vs DFS/BFS:
        - Single query: DFS/BFS is simpler
        - Multiple queries: Union-Find is more efficient (preprocess once)
        - Dynamic connectivity: Union-Find handles edge additions
        """
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]

        def union(x: int, y: int) -> None:
            px, py = find(x), find(y)
            if px == py:
                return
            # Union by rank
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1

        # Union all edges
        for u, v in edges:
            union(u, v)

        # Check if same component
        return find(source) == find(destination)

# DFS: Simple reachability, recursive thinking
# - Easy to implement
# - Good for single query
# - Natural for exploring all paths

# BFS: Need shortest path or level information
# - Guaranteed shortest path in unweighted graph
# - Good for single query
# - Level-by-level exploration

# Union-Find: Multiple connectivity queries
# - Preprocess graph once
# - O(α(n)) per query after preprocessing
# - Handles edge additions efficiently

# Grid traversal setup
rows, cols = len(grid), len(grid[0])
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def is_valid(r: int, c: int) -> bool:
    return 0 <= r < rows and 0 <= c < cols

# Common patterns:
# - Mark visited in-place: grid[r][c] = '#' or '0'
# - Use visited set: visited.add((r, c))
# - Check condition: grid[r][c] == target_value

def count_components(grid: List[List[str]]) -> int:
    """Count connected components in a grid."""
    if not grid:
        return 0

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

    def dfs(row: int, col: int) -> None:
        if (row < 0 or row >= rows or col < 0 or col >= cols or
            grid[row][col] != '1'):
            return
        grid[row][col] = '0'  # Mark visited
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count

from collections import deque

def shortest_path(graph: dict[int, list[int]], start: int, end: int) -> int:
    """Find shortest path in unweighted graph. Returns -1 if unreachable."""
    if start == end:
        return 0

    visited = {start}
    queue = deque([(start, 0)])  # (node, distance)

    while queue:
        node, dist = queue.popleft()

        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1

from collections import deque

def multi_source_bfs(grid: List[List[int]], sources: List[tuple[int, int]]) -> int:
    """BFS from multiple sources simultaneously. Returns max distance."""
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    visited = set(sources)
    queue = deque(sources)
    distance = 0

    while queue:
        distance += 1
        for _ in range(len(queue)):  # Process level by level
            row, col = queue.popleft()

            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols and
                    (nr, nc) not in visited and grid[nr][nc] == 1):
                    visited.add((nr, nc))
                    queue.append((nr, nc))

    return distance - 1  # Adjust for initial increment

def clone_graph(node: 'Node') -> 'Node':
    """Deep copy a graph using DFS."""
    if not node:
        return None

    old_to_new: dict[Node, Node] = {}

    def dfs(original: 'Node') -> 'Node':
        if original in old_to_new:
            return old_to_new[original]

        clone = Node(original.val)
        old_to_new[original] = clone

        for neighbor in original.neighbors:
            clone.neighbors.append(dfs(neighbor))

        return clone

    return dfs(node)

from collections import deque

def is_bipartite(graph: List[List[int]]) -> bool:
    """Check if graph is bipartite using BFS coloring."""
    n = len(graph)
    color = [-1] * n  # -1 = uncolored

    def bfs(start: int) -> bool:
        queue = deque([start])
        color[start] = 0

        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
        return True

    for node in range(n):
        if color[node] == -1:
            if not bfs(node):
                return False

    return True

def can_reach(graph: dict[int, list[int]], start: int, target: int) -> bool:
    """Check if target is reachable from start."""
    visited = set()

    def dfs(node: int) -> bool:
        if node == target:
            return True
        if node in visited:
            return False

        visited.add(node)

        for neighbor in graph.get(node, []):
            if dfs(neighbor):
                return True

        return False

    return dfs(start)