


from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

lowerCAmelCase__ :			str         ={
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				{start}
			SCREAMING_SNAKE_CASE_		:    int 		=				[start]
			SCREAMING_SNAKE_CASE_		:    Queue 		=				Queue()
			queue.put(A__							)
			while not queue.empty():
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.get()
						for w in graph[v]:
									if w not in explored:
												explored.add(A__							)
												result.append(A__							)
												queue.put(A__							)
			return result






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Any 		=				{start}
			SCREAMING_SNAKE_CASE_		:    str 		=				[start]
			SCREAMING_SNAKE_CASE_		:    List[Any] 		=				deque([start]							)
			while queue:
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.popleft()
						for child in graph[v]:
									if child not in visited:
												visited.add(A__							)
												result.append(A__							)
												queue.append(A__							)
			return result






def 	a__ (							A__							):
			SCREAMING_SNAKE_CASE_		:    List[str] 		=				F'''from __main__ import G, {name}'''
			SCREAMING_SNAKE_CASE_		:    Tuple 		=				1_0_0_0_0
			SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				timeit(F'''{name}(G, \'A\')''',			setup=A__,			number=A__							)
			print(F'''{name:<35} finished {number} runs in {res:.5f} seconds'''							)


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				benchmark_function('breadth_first_search')
				benchmark_function('breadth_first_search_with_deque')
				# breadth_first_search                finished 10000 runs in 0.20999 seconds
				# breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds









from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

lowerCAmelCase__ :			str         ={
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				{start}
			SCREAMING_SNAKE_CASE_		:    int 		=				[start]
			SCREAMING_SNAKE_CASE_		:    Queue 		=				Queue()
			queue.put(A__							)
			while not queue.empty():
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.get()
						for w in graph[v]:
									if w not in explored:
												explored.add(A__							)
												result.append(A__							)
												queue.put(A__							)
			return result






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Any 		=				{start}
			SCREAMING_SNAKE_CASE_		:    str 		=				[start]
			SCREAMING_SNAKE_CASE_		:    List[Any] 		=				deque([start]							)
			while queue:
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.popleft()
						for child in graph[v]:
									if child not in visited:
												visited.add(A__							)
												result.append(A__							)
												queue.append(A__							)
			return result






def 	a__ (							A__							):
			SCREAMING_SNAKE_CASE_		:    List[str] 		=				F'''from __main__ import G, {name}'''
			SCREAMING_SNAKE_CASE_		:    Tuple 		=				1_0_0_0_0
			SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				timeit(F'''{name}(G, \'A\')''',			setup=A__,			number=A__							)
			print(F'''{name:<35} finished {number} runs in {res:.5f} seconds'''							)


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				benchmark_function('breadth_first_search')
				benchmark_function('breadth_first_search_with_deque')
				# breadth_first_search                finished 10000 runs in 0.20999 seconds
				# breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds





