


'''simple docstring'''





from __future__ import annotations

from typing import Generic, TypeVar

__lowerCamelCase												=						TypeVar('''T''')




class 				UpperCAmelCase			(			Generic[T]						):


 def __init__(      self							:	Dict			,       __lowerCamelCase							:	T ):
    UpperCAmelCase__	:Any      =      data
    UpperCAmelCase__	:Dict      =      self
    UpperCAmelCase__	:Optional[Any]      =      0




class 				UpperCAmelCase			(			Generic[T]						):


 def __init__(      self							:	Optional[int] ):
    # map from node name to the node object
    UpperCAmelCase__	:dict[T, DisjointSetTreeNode[T]]      =      {}


 def        __SCREAMING_SNAKE_CASE					(      self							:	List[str]			,       __lowerCamelCase							:	T ):
    # create a new set with x as its member
    UpperCAmelCase__	:Any      =      DisjointSetTreeNode(__lowerCamelCase )


 def        __SCREAMING_SNAKE_CASE					(      self							:	Optional[int]			,       __lowerCamelCase							:	T ):
    # find the set x belongs to (with path-compression)
    UpperCAmelCase__	:Optional[int]      =      self.map[data]
    if elem_ref != elem_ref.parent:
       UpperCAmelCase__	:Optional[int]      =      self.find_set(elem_ref.parent.data )
    return elem_ref.parent


 def        __SCREAMING_SNAKE_CASE					(      self							:	int			,       __lowerCamelCase							:	DisjointSetTreeNode[T]			,       __lowerCamelCase							:	DisjointSetTreeNode[T] ):
    # helper function for union operation
    if nodea.rank > nodea.rank:
       UpperCAmelCase__	:Any      =      nodea
    else:
       UpperCAmelCase__	:Optional[int]      =      nodea
       if nodea.rank == nodea.rank:
          nodea.rank += 1





 def        __SCREAMING_SNAKE_CASE					(      self							:	List[str]			,       __lowerCamelCase							:	T			,       __lowerCamelCase							:	T ):
    # merge 2 disjoint sets
    self.link(self.find_set(__lowerCamelCase )			,       self.find_set(__lowerCamelCase ) )




class 				UpperCAmelCase			(			Generic[T]						):


 def __init__(      self							:	Union[str, Any] ):
    # connections: map from the node to the neighbouring nodes (with weights)
    UpperCAmelCase__	:dict[T, dict[T, int]]      =      {}


 def        __SCREAMING_SNAKE_CASE					(      self							:	Any			,       __lowerCamelCase							:	T ):
    # add a node ONLY if its not present in the graph
    if node not in self.connections:
       UpperCAmelCase__	:Dict      =      {}


 def        __SCREAMING_SNAKE_CASE					(      self							:	Union[str, Any]			,       __lowerCamelCase							:	T			,       __lowerCamelCase							:	T			,       __lowerCamelCase							:	int ):
    # add an edge with the given weight
    self.add_node(__lowerCamelCase )
    self.add_node(__lowerCamelCase )
    UpperCAmelCase__	:Union[str, Any]      =      weight
    UpperCAmelCase__	:Dict      =      weight





 def        __SCREAMING_SNAKE_CASE					(      self							:	Union[str, Any] ):
    UpperCAmelCase__	:Tuple      =      []
    UpperCAmelCase__	:List[Any]      =      set()
    for start in self.connections:
       for end in self.connections[start]:
          if (start, end) not in seen:
             seen.add((end, start) )
             edges.append((start, end, self.connections[start][end]) )
    edges.sort(key=lambda __lowerCamelCase : x[2] )

    # creating the disjoint set
    UpperCAmelCase__	:List[Any]      =      DisjointSetTree[T]()
    for node in self.connections:
       disjoint_set.make_set(__lowerCamelCase )

    # MST generation
    UpperCAmelCase__	:str      =      0
    UpperCAmelCase__	:Union[str, Any]      =      0
    UpperCAmelCase__	:Optional[Any]      =      GraphUndirectedWeighted[T]()
    while num_edges < len(self.connections ) - 1:
       UpperCAmelCase__   ,						UpperCAmelCase__   ,						UpperCAmelCase__	:Optional[int]      =      edges[index]
       index += 1
       UpperCAmelCase__	:int      =      disjoint_set.find_set(__lowerCamelCase )
       UpperCAmelCase__	:Tuple      =      disjoint_set.find_set(__lowerCamelCase )
       if parent_u != parent_v:
          num_edges += 1
          graph.add_edge(__lowerCamelCase			,       __lowerCamelCase			,       __lowerCamelCase )
          disjoint_set.union(__lowerCamelCase			,       __lowerCamelCase )
    return graph







'''simple docstring'''





def        a__     (					UpperCamelCase_						:      int | float | str						):
   try:
      UpperCAmelCase__	:Union[str, Any]      =      float(UpperCamelCase_						)
   except ValueError:
      raise ValueError('''Please enter a valid number'''						)
   UpperCAmelCase__	:List[str]      =      decimal - int(UpperCamelCase_						)
   if fractional_part == 0:
      return int(UpperCamelCase_						), 1
   else:
      UpperCAmelCase__	:List[Any]      =      len(str(UpperCamelCase_						).split('''.'''						)[1]						)
      UpperCAmelCase__	:Tuple      =      int(decimal * (10**number_of_frac_digits)						)
      UpperCAmelCase__	:int      =      10**number_of_frac_digits
      UpperCAmelCase__   ,						UpperCAmelCase__	:List[str]      =      denominator, numerator
      while True:
         UpperCAmelCase__	:Optional[Any]      =      dividend % divisor
         if remainder == 0:
            break
         UpperCAmelCase__   ,						UpperCAmelCase__	:List[str]      =      divisor, remainder
      UpperCAmelCase__   ,						UpperCAmelCase__	:Tuple      =      numerator / divisor, denominator / divisor
      return int(UpperCamelCase_						), int(UpperCamelCase_						)


if __name__ == "__main__":
    print(F'''{decimal_to_fraction(2) = }''')
    print(F'''{decimal_to_fraction(89.0) = }''')
    print(F'''{decimal_to_fraction("67") = }''')
    print(F'''{decimal_to_fraction("45.0") = }''')
    print(F'''{decimal_to_fraction(1.5) = }''')
    print(F'''{decimal_to_fraction("6.25") = }''')
    print(F'''{decimal_to_fraction("78td") = }''')



