




from __future__ import annotations

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

__a  :		List[str]		     =   {
    '''A''': ['''B''', '''C'''],
    '''B''': ['''A''', '''D''', '''E'''],
    '''C''': ['''A''', '''F'''],
    '''D''': ['''B'''],
    '''E''': ['''B''', '''F'''],
    '''F''': ['''C''', '''E'''],
}
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			list[str]:
							lowercase__  :	Any        =							{start}
							lowercase__  :	int        =							[start]
							lowercase__  :	Queue        =							Queue()
							queue.put(SCREAMING_SNAKE_CASE_    )
							while not queue.empty():
														lowercase__  :	List[Any]        =							queue.get()
														for w in graph[v]:
																					if w not in explored:
																												explored.add(SCREAMING_SNAKE_CASE_    )
																												result.append(SCREAMING_SNAKE_CASE_    )
																												queue.put(SCREAMING_SNAKE_CASE_    )
							return result
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			list[str]:
							lowercase__  :	List[Any]        =							{start}
							lowercase__  :	List[str]        =							[start]
							lowercase__  :	Union[str, Any]        =							deque([start]    )
							while queue:
														lowercase__  :	Union[str, Any]        =							queue.popleft()
														for child in graph[v]:
																					if child not in visited:
																												visited.add(SCREAMING_SNAKE_CASE_    )
																												result.append(SCREAMING_SNAKE_CASE_    )
																												queue.append(SCREAMING_SNAKE_CASE_    )
							return result
def  snake_case_					(		SCREAMING_SNAKE_CASE_    )      ->			None:
							lowercase__  :	Tuple        =							F"""from __main__ import G, {name}"""
							lowercase__  :	Dict        =							1_00_00
							lowercase__  :	Tuple        =							timeit(F"""{name}(G, 'A')"""    ,setup=SCREAMING_SNAKE_CASE_    ,number=SCREAMING_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





from __future__ import annotations

import math
import random
def  snake_case_					(		SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    ,SCREAMING_SNAKE_CASE_    )      ->			list[int]:
							lowercase__  :	List[Any]        =							d * e - 1
							lowercase__  :	Any        =							0
							lowercase__  :	Dict        =							0
							while p == 0:
														lowercase__  :	Dict        =							random.randint(2    ,n - 1    )
														lowercase__  :	int        =							k
														while True:
																					if t % 2 == 0:
																												lowercase__  :	str        =							t // 2
																												lowercase__  :	int        =							(g**t) % n
																												lowercase__  :	List[Any]        =							math.gcd(x - 1    ,SCREAMING_SNAKE_CASE_    )
																												if x > 1 and y > 1:
																																			lowercase__  :	Any        =							y
																																			lowercase__  :	Optional[int]        =							n // y
																																			break  # find the correct factors
																					else:
																												break  # t is not divisible by 2, break and choose another g
							return sorted([p, q]    )


if __name__ == "__main__":
						import doctest

						doctest.testmod()