



"""simple docstring"""




from __future__ import annotations

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

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


def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase					)  ->      list[str]:






      '''simple docstring'''


      lowercase	:   Union[str, Any]											= {start}
      lowercase	:   int											= [start]
      lowercase	:   Queue											= Queue()
      queue.put(_UpperCAmelCase					)
      while not queue.empty():
            lowercase	:   Any											= queue.get()
            for w in graph[v]:
                  if w not in explored:
                        explored.add(_UpperCAmelCase					)
                        result.append(_UpperCAmelCase					)
                        queue.put(_UpperCAmelCase					)
      return result


def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase					)  ->      list[str]:






      '''simple docstring'''


      lowercase	:   Dict											= {start}
      lowercase	:   Optional[int]											= [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(_UpperCAmelCase					)
                        result.append(_UpperCAmelCase					)
                        queue.append(_UpperCAmelCase					)
      return result


def 	lowercase__  (      _UpperCAmelCase					)  ->      None:






      '''simple docstring'''


      lowercase	:   Tuple											= f'''from __main__ import G, {name}'''
      lowercase	:   List[Any]											= 1_00_00
      lowercase	:   int											= 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"""




from __future__ import annotations


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      lowercase	:   Optional[Any]											= [0] * max_one

      for i in range(0						,   _UpperCAmelCase					):
            lowercase	:   List[Any]											= i

      for i in range(2						,   _UpperCAmelCase					):
            if totients[i] == i:
                  for j in range(_UpperCAmelCase						,   _UpperCAmelCase						,   _UpperCAmelCase					):
                        totients[j] -= totients[j] // i

      return totients


def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase					)  ->      bool:






      '''simple docstring'''


      return sorted(str(_UpperCAmelCase					)					) == sorted(str(_UpperCAmelCase					)					)


def 	lowercase__  (      _UpperCAmelCase = 10_00_00_00					)  ->      int:






      '''simple docstring'''


      lowercase	:   Union[str, Any]											= 1  # i
      lowercase	:   Any											= 0  # φ(i)
      lowercase	:   int											= get_totients(max_n + 1					)

      for i in range(2						,   max_n + 1					):
            lowercase	:   Any											= totients[i]

            if i * min_denominator < min_numerator * t and has_same_digits(_UpperCAmelCase						,   _UpperCAmelCase					):
                  lowercase	:   List[Any]											= i
                  lowercase	:   Optional[Any]											= t

      return min_numerator


if __name__ == "__main__":
     print(f'''{solution() = }''')
