

from __future__ import annotations

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

_UpperCamelCase     =    {
    '''A''': ['''B''', '''C'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F'''],
    '''D''': ['''B'''],
    '''E''': ['''B''', '''F'''],
    '''F''': ['''C''', '''E'''],
}
def 		UpperCamelCase_(    snake_case__:						dict						,					snake_case__:						str     ) ->				list[str]:
 UpperCAmelCase__           =       {start}
 UpperCAmelCase__           =       [start]
 UpperCAmelCase__           =       Queue()
 queue.put(snake_case__     )
 while not queue.empty():
  UpperCAmelCase__           =       queue.get()
  for w in graph[v]:
   if w not in explored:
    explored.add(snake_case__     )
    result.append(snake_case__     )
    queue.put(snake_case__     )
 return result
def 		UpperCamelCase_(    snake_case__:						dict						,					snake_case__:						str     ) ->				list[str]:
 UpperCAmelCase__           =       {start}
 UpperCAmelCase__           =       [start]
 UpperCAmelCase__           =       deque([start]     )
 while queue:
  UpperCAmelCase__           =       queue.popleft()
  for child in graph[v]:
   if child not in visited:
    visited.add(snake_case__     )
    result.append(snake_case__     )
    queue.append(snake_case__     )
 return result
def 		UpperCamelCase_(    snake_case__:						str     ) ->				None:
 UpperCAmelCase__           =       f"from __main__ import G, {name}"
 UpperCAmelCase__           =       1_00_00
 UpperCAmelCase__           =       timeit(f"{name}(G, 'A')"						,					setup=snake_case__						,					number=snake_case__     )
 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






def 		UpperCamelCase_(    snake_case__:						int     ) ->				int:
 if not isinstance(snake_case__						,					snake_case__     ):
  UpperCAmelCase__           =       f"Input value of [number={number}] must be an integer"
  raise TypeError(snake_case__     )
 if number < 1:
  raise ValueError('Input must be a positive integer'     )
 return number * (2 * number - 1)


if __name__ == "__main__":
 import doctest

 doctest.testmod()



