

from __future__ import annotations

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

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




def 						_A						(						UpperCamelCase_  : dict,    UpperCamelCase_  : str)			->		list[str]:
   '''simple docstring'''


   __lowercase			=		{start}
   __lowercase			=		[start]
   __lowercase			=		Queue()
   queue.put(UpperCamelCase_)
   while not queue.empty():
      __lowercase			=		queue.get()
      for w in graph[v]:
         if w not in explored:
            explored.add(UpperCamelCase_)
            result.append(UpperCamelCase_)
            queue.put(UpperCamelCase_)
   return result




def 						_A						(						UpperCamelCase_  : dict,    UpperCamelCase_  : str)			->		list[str]:
   '''simple docstring'''


   __lowercase			=		{start}
   __lowercase			=		[start]
   __lowercase			=		deque([start])
   while queue:
      __lowercase			=		queue.popleft()
      for child in graph[v]:
         if child not in visited:
            visited.add(UpperCamelCase_)
            result.append(UpperCamelCase_)
            queue.append(UpperCamelCase_)
   return result




def 						_A						(						UpperCamelCase_  : str)			->		None:
   '''simple docstring'''


   __lowercase			=		F"""from __main__ import G, {name}"""
   __lowercase			=		10000
   __lowercase			=		timeit(F"""{name}(G, 'A')""",    setup=UpperCamelCase_,    number=UpperCamelCase_)
   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







"""simple docstring"""





def 						_A						(						UpperCamelCase_  : list,    UpperCamelCase_  : list,    UpperCamelCase_  : list,    UpperCamelCase_  : int,    UpperCamelCase_  : int)			->		None:
   '''simple docstring'''


   if target == 0:
      answer.append(path.copy())
   else:
      for index in range(UpperCamelCase_,    len(UpperCamelCase_)):
         if target >= candidates[index]:
            path.append(candidates[index])
            backtrack(UpperCamelCase_,    UpperCamelCase_,    UpperCamelCase_,    target - candidates[index],    UpperCamelCase_)
            path.pop(len(UpperCamelCase_) - 1)




def 						_A						(						UpperCamelCase_  : list,    UpperCamelCase_  : int)			->		list:
   '''simple docstring'''


   __lowercase			=		[]  # type: list[int]
   __lowercase			=		[]  # type: list[int]
   backtrack(UpperCamelCase_,    UpperCamelCase_,    UpperCamelCase_,    UpperCamelCase_,    0)
   return answer




def 						_A						(						)			->		None:
   '''simple docstring'''


   print(combination_sum([-8, 2.3, 0],    1))


if __name__ == "__main__":
   import doctest

   doctest.testmod()
   main()




