





from __future__ import annotations

from fractions import Fraction
from math import gcd, sqrt

def     a_       (					lowerCAmelCase_ :     int      ):
   __lowerCAmelCase				      =      int(number**0.5      )
   return number == sq * sq

def     a_       (					lowerCAmelCase_ :     int,      lowerCAmelCase_ :     int,      lowerCAmelCase_ :     int,      lowerCAmelCase_ :     int,      lowerCAmelCase_ :     int,      lowerCAmelCase_ :     int      ):
   __lowerCAmelCase				      =      x_num * y_den * z_den + y_num * x_den * z_den + z_num * x_den * y_den
   __lowerCAmelCase				      =      x_den * y_den * z_den
   __lowerCAmelCase				      =      gcd(lowerCAmelCase_,      lowerCAmelCase_      )
   top //= hcf
   bottom //= hcf
   return top, bottom

def     a_       (					lowerCAmelCase_ :     int = 35      ):
   __lowerCAmelCase				      =      set()
   __lowerCAmelCase				      =      42
   __lowerCAmelCase				      =      Fraction(0      )
   __lowerCAmelCase				      =      42

   for x_num in range(1,      order + 1      ):
      for x_den in range(x_num + 1,      order + 1      ):
         for y_num in range(1,      order + 1      ):
            for y_den in range(y_num + 1,      order + 1      ):
               # n=1
               __lowerCAmelCase				      =      x_num * y_den + x_den * y_num
               __lowerCAmelCase				      =      x_den * y_den
               __lowerCAmelCase				      =      gcd(lowerCAmelCase_,      lowerCAmelCase_      )
               z_num //= hcf
               z_den //= hcf
               if 0 < z_num < z_den <= order:
                  __lowerCAmelCase				      =      add_three(
                      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_      )
                  unique_s.add(lowerCAmelCase_      )

               # n=2
               __lowerCAmelCase				      =      (
                   x_num * x_num * y_den * y_den + x_den * x_den * y_num * y_num
               )
               __lowerCAmelCase				      =      x_den * x_den * y_den * y_den
               if is_sq(lowerCAmelCase_      ) and is_sq(lowerCAmelCase_      ):
                  __lowerCAmelCase				      =      int(sqrt(lowerCAmelCase_      )      )
                  __lowerCAmelCase				      =      int(sqrt(lowerCAmelCase_      )      )
                  __lowerCAmelCase				      =      gcd(lowerCAmelCase_,      lowerCAmelCase_      )
                  z_num //= hcf
                  z_den //= hcf
                  if 0 < z_num < z_den <= order:
                     __lowerCAmelCase				      =      add_three(
                         lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_      )
                     unique_s.add(lowerCAmelCase_      )

                    # n=-1
               __lowerCAmelCase				      =      x_num * y_num
               __lowerCAmelCase				      =      x_den * y_num + x_num * y_den
               __lowerCAmelCase				      =      gcd(lowerCAmelCase_,      lowerCAmelCase_      )
               z_num //= hcf
               z_den //= hcf
               if 0 < z_num < z_den <= order:
                  __lowerCAmelCase				      =      add_three(
                      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_      )
                  unique_s.add(lowerCAmelCase_      )

               # n=2
               __lowerCAmelCase				      =      x_num * x_num * y_num * y_num
               __lowerCAmelCase				      =      (
                   x_den * x_den * y_num * y_num + x_num * x_num * y_den * y_den
               )
               if is_sq(lowerCAmelCase_      ) and is_sq(lowerCAmelCase_      ):
                  __lowerCAmelCase				      =      int(sqrt(lowerCAmelCase_      )      )
                  __lowerCAmelCase				      =      int(sqrt(lowerCAmelCase_      )      )
                  __lowerCAmelCase				      =      gcd(lowerCAmelCase_,      lowerCAmelCase_      )
                  z_num //= hcf
                  z_den //= hcf
                  if 0 < z_num < z_den <= order:
                     __lowerCAmelCase				      =      add_three(
                         lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_,      lowerCAmelCase_      )
                     unique_s.add(lowerCAmelCase_      )

   for num, den in unique_s:
      total += Fraction(lowerCAmelCase_,      lowerCAmelCase_      )

   return total.denominator + total.numerator


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


"""simple docstring"""






from __future__ import annotations


def      UpperCAmelCase__			(							lowerCAmelCase__	:dict   ,						lowerCAmelCase__	:str						)					->       set[str]:
      '''simple docstring'''


      lowercase				,				lowercase								=      set(lowerCAmelCase__						), [start]

      while stack:
            lowercase								=      stack.pop()
            explored.add(lowerCAmelCase__						)
            # Differences from BFS:
            # 1) pop last element instead of first one
            # 2) add adjacent elements to stack without exploring them
            for adj in reversed(graph[v]						):
                  if adj not in explored:
                        stack.append(lowerCAmelCase__						)
      return explored


__lowerCAmelCase       :			str   	={
    """A""": ["""B""", """C""", """D"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F"""],
    """D""": ["""B""", """D"""],
    """E""": ["""B""", """F"""],
    """F""": ["""C""", """E""", """G"""],
    """G""": ["""F"""],
}

if __name__ == "__main__":
       import doctest

       doctest.testmod()
       print(depth_first_search(G, """A"""))



