from typing import Dict
from typing import List
from typing import Optional
import queue


def find_node_distance(
    i: int, vertex_connections: Dict[int, List[int]], target: Optional[int] = None
):
    """
    Finds the distances from one node to all others.
    Args:
        i: starting vertex idx
        vertex_connections: expects the vertices to be in a range starting from zero.
        target:
    Returns: distance between vertex i and target, if target is not None.
             Otherwise the distance to every other node.
    """
    # visited[n] for keeping track of visited node in BFS
    visited = [False] * len(vertex_connections.keys())
    # Initialize distances as 0
    distance = [0] * len(vertex_connections.keys())
    # queue to do BFS
    queue_: queue.Queue = queue.Queue()
    distance[i] = 0
    queue_.put(i)
    visited[i] = True
    while not queue_.empty():
        x = queue_.get()
        for i in range(len(vertex_connections[x])):
            if visited[vertex_connections[x][i]]:
                continue
            # update distance for i
            distance[vertex_connections[x][i]] = distance[x] + 1
            queue_.put(vertex_connections[x][i])
            visited[vertex_connections[x][i]] = True
    if target is not None:
        return distance[target]
    else:
        return distance