from queue import Queue
from itertools import count
from typing import TypeVar, Generic, Optional
from import Mapping
from dataclasses import dataclass, field

T = TypeVar('T')
VertexId = int
Adjacencies = Mapping[VertexId, VertexId]

class Vertex(Generic[T]):
    value: T
    id: VertexId = field(default_factory=count().__next__)

Vertices = Mapping[VertexId, Vertex]

def breadth_first_search(root_id: VertexId, target_id: VertexId, graph: Adjacencies, vertices: Vertices) -> Optional[Vertex]:
    """Search for TARGET within GRAPH using breadth-first search."""
    queue = Queue()
    visited = set()

    while not queue.empty():
        current_id = queue.get()

        if current_id == target_id:
            return vertices[current_id]

        if current_id in visited:

        if current_id in adjacencies:
            for neighbor_id in [id for id in adjacencies[current_id]]:

    return None

a = Vertex(value='a')
b = Vertex(value='b')
c = Vertex(value='c')
d = Vertex(value='d')
e = Vertex(value='e')
f = Vertex(value='f')
adjacencies = { {,}, {}, {,},
vertices = { a, b, c, d, e, f,
print(breadth_first_search(,, adjacencies, vertices), 'should be a')
print(breadth_first_search(,, adjacencies, vertices), 'should be e')
print(breadth_first_search(,, adjacencies, vertices), 'should be None')
print(breadth_first_search(, 100, adjacencies, vertices), 'should be None')