Graph Traversal (BFS & DFS)

from collections import deque, defaultdict

def bfs_shortest_path(edges: list[list[int]], start: int, target: int) -> int:
    # 1. Build adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        
    # 2. Queue stores (current_node, distance)
    queue = deque([(start, 0)])
    visited = {start}  # ALWAYS mark visited at enqueue time
    
    while queue:
        curr, dist = queue.popleft()
        if curr == target:
            return dist
            
        for neighbor in graph[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
                
    return -1  # Target unreachable