def dfs(graph: Dict[int, List[int]], start: int) -> Set[int]:
    """
    DFS to find all reachable nodes.
    Time: O(V + E), Space: O(V)
    """
    visited = set()
    
    def explore(node: int):
        if node in visited:
            return
        
        visited.add(node)
        
        for neighbor in graph.get(node, []):
            explore(neighbor)
    
    explore(start)
    return visited

def dfs_iterative(graph: Dict[int, List[int]], start: int) -> Set[int]:
    """
    Iterative DFS using explicit stack.
    Time: O(V + E), Space: O(V)
    """
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if node in visited:
            continue
        
        visited.add(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                stack.append(neighbor)
    
    return visited

from collections import deque

def bfs(graph: Dict[int, List[int]], start: int) -> Dict[int, int]:
    """
    BFS to find shortest distance to all nodes.
    Time: O(V + E), Space: O(V)
    """
    visited = {start}
    queue = deque([(start, 0)])  # (node, distance)
    distances = {start: 0}
    
    while queue:
        node, dist = queue.popleft()
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                distances[neighbor] = dist + 1
                queue.append((neighbor, dist + 1))
    
    return distances

def cloneGraph(node: 'Node') -> 'Node':
    """
    Deep clone graph using DFS with hash map.
    Time: O(V + E), Space: O(V)
    """
    if not node:
        return None
    
    cloned = {}  # old_node -> new_node
    
    def dfs(node):
        if node in cloned:
            return cloned[node]
        
        # Create clone
        clone = Node(node.val)
        cloned[node] = clone
        
        # Clone neighbors
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone
    
    return dfs(node)

def topologicalSort(n: int, edges: List[List[int]]) -> List[int]:
    """
    Topological sort using BFS (Kahn's algorithm).
    Time: O(V + E), Space: O(V + E)
    """
    # Build graph and indegree count
    graph = defaultdict(list)
    indegree = [0] * n
    
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    
    # Start with nodes having no incoming edges
    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        # Remove edges from this node
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if valid (no cycles)
    return result if len(result) == n else []

def gridBFS(grid: List[List[int]], start: Tuple[int, int]) -> int:
    """
    BFS on grid - treat as implicit graph.
    Time: O(rows * cols), Space: O(rows * cols)
    """
    rows, cols = len(grid), len(grid[0])
    directions = [(0,1), (1,0), (0,-1), (-1,0)]  # right, down, left, up
    
    visited = {start}
    queue = deque([start])
    distance = 0
    
    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            
            # Check if reached target
            if grid[r][c] == TARGET:
                return distance
            
            # Explore neighbors
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                # Check bounds and obstacles
                if (0 <= nr < rows and 0 <= nc < cols and
                    (nr, nc) not in visited and
                    grid[nr][nc] != OBSTACLE):
                    
                    visited.add((nr, nc))
                    queue.append((nr, nc))
        
        distance += 1
    
    return -1  # Target not reachable

class UnionFind:
    """Union-Find with path compression and union by rank."""
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n
    
    def find(self, x: int) -> int:
        """Find with path compression."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        """Union by rank. Returns True if merged."""
        px, py = self.find(x), self.find(y)
        
        if px == py:
            return False  # Already connected
        
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        
        self.components -= 1
        return True

def bidirectionalBFS(start: str, end: str, neighbors_func) -> int:
    """
    BFS from both ends - faster for long paths.
    Time: O(b^(d/2)) vs O(b^d) for regular BFS
    """
    if start == end:
        return 0
    
    front = {start}
    back = {end}
    visited = {start, end}
    distance = 1
    
    while front and back:
        # Always expand smaller frontier
        if len(front) > len(back):
            front, back = back, front
        
        next_front = set()
        
        for node in front:
            for neighbor in neighbors_func(node):
                if neighbor in back:
                    return distance
                
                if neighbor not in visited:
                    visited.add(neighbor)
                    next_front.add(neighbor)
        
        front = next_front
        distance += 1
    
    return -1