'''simple docstring'''




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 __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       )			->					list[str]:
    __lowerCamelCase						=						{start}
    __lowerCamelCase						=						[start]
    __lowerCamelCase						=						Queue()
    queue.put(UpperCamelCase__       )
    while not queue.empty():
        __lowerCamelCase						=						queue.get()
        for w in graph[v]:
            if w not in explored:
                explored.add(UpperCamelCase__       )
                result.append(UpperCamelCase__       )
                queue.put(UpperCamelCase__       )
    return result






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       )			->					list[str]:
    __lowerCamelCase						=						{start}
    __lowerCamelCase						=						[start]
    __lowerCamelCase						=						deque([start]       )
    while queue:
        __lowerCamelCase						=						queue.popleft()
        for child in graph[v]:
            if child not in visited:
                visited.add(UpperCamelCase__       )
                result.append(UpperCamelCase__       )
                queue.append(UpperCamelCase__       )
    return result






def __lowerCAmelCase				(							UpperCamelCase__       )			->					None:
    __lowerCamelCase						=						f"""from __main__ import G, {name}"""
    __lowerCamelCase						=						1_00_00
    __lowerCamelCase						=						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 __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__       )			->					tuple[float, float]:
    assert (
        c % greatest_common_divisor(UpperCamelCase__       ,						UpperCamelCase__       ) == 0
    )  # greatest_common_divisor(a,b) function implemented below
    ((__lowerCamelCase)			,						(__lowerCamelCase)			,						(__lowerCamelCase))						=						extended_gcd(UpperCamelCase__       ,						UpperCamelCase__       )  # extended_gcd(a,b) function implemented below
    __lowerCamelCase						=						c / d
    return (r * x, r * y)






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__ = 2       )			->					None:
    ((__lowerCamelCase)			,						(__lowerCamelCase))						=						diophantine(UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__       )  # Initial value
    __lowerCamelCase						=						greatest_common_divisor(UpperCamelCase__       ,						UpperCamelCase__       )
    __lowerCamelCase						=						a // d
    __lowerCamelCase						=						b // d

    for i in range(UpperCamelCase__       ):
        __lowerCamelCase						=						xa + i * q
        __lowerCamelCase						=						ya - i * p
        print(UpperCamelCase__       ,						UpperCamelCase__       )






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       )			->					int:
    if a < b:
        __lowerCamelCase			,						__lowerCamelCase						=						b, a

    while a % b != 0:
        __lowerCamelCase			,						__lowerCamelCase						=						b, a % b

    return b






def __lowerCAmelCase				(							UpperCamelCase__       ,						UpperCamelCase__       )			->					tuple[int, int, int]:
    assert a >= 0 and b >= 0

    if b == 0:
        __lowerCamelCase			,						__lowerCamelCase			,						__lowerCamelCase						=						a, 1, 0
    else:
        ((__lowerCamelCase)			,						(__lowerCamelCase)			,						(__lowerCamelCase))						=						extended_gcd(UpperCamelCase__       ,						a % b       )
        __lowerCamelCase						=						q
        __lowerCamelCase						=						p - q * (a // b)

    assert a % d == 0 and b % d == 0
    assert d == a * x + b * y

    return (d, x, y)


if __name__ == "__main__":
  from doctest import testmod

  testmod(name="diophantine", verbose=True)
  testmod(name="diophantine_all_soln", verbose=True)
  testmod(name="extended_gcd", verbose=True)
  testmod(name="greatest_common_divisor", verbose=True)
