



'''simple docstring'''


from __future__ import annotations

from typing import Generic, TypeVar

_lowerCamelCase	:       List[str]      	=	TypeVar("T")

class  SCREAMING_SNAKE_CASE (  Generic[T]		):






    """simple docstring"""





    def __init__(  self      :					Optional[int]  ,						UpperCamelCase__      :					T ):


       """simple docstring"""







       UpperCamelCase					=  data
       UpperCamelCase					=  self
       UpperCamelCase					=  0

class  SCREAMING_SNAKE_CASE (  Generic[T]		):






    """simple docstring"""





    def __init__(  self      :					Dict ):


       """simple docstring"""







       UpperCamelCase					=  {}






    def  A       (  self      :					Dict  ,						UpperCamelCase__      :					T ):


       """simple docstring"""







       UpperCamelCase					=  DisjointSetTreeNode(_lowerCamelCase )






    def  A       (  self      :					Optional[int]  ,						UpperCamelCase__      :					T ):


       """simple docstring"""







       UpperCamelCase					=  self.map[data]
       if elem_ref != elem_ref.parent:
          UpperCamelCase					=  self.find_set(elem_ref.parent.data )
       return elem_ref.parent






    def  A       (  self      :					Any  ,						UpperCamelCase__      :					DisjointSetTreeNode[T]  ,						UpperCamelCase__      :					DisjointSetTreeNode[T] ):


       """simple docstring"""







       if nodea.rank > nodea.rank:
          UpperCamelCase					=  nodea
       else:
          UpperCamelCase					=  nodea
          if nodea.rank == nodea.rank:
             nodea.rank += 1






    def  A       (  self      :					Optional[int]  ,						UpperCamelCase__      :					T  ,						UpperCamelCase__      :					T ):


       """simple docstring"""







       self.link(self.find_set(_lowerCamelCase )  ,						self.find_set(_lowerCamelCase ) )

class  SCREAMING_SNAKE_CASE (  Generic[T]		):






    """simple docstring"""





    def __init__(  self      :					Dict ):


       """simple docstring"""







       UpperCamelCase					=  {}






    def  A       (  self      :					str  ,						UpperCamelCase__      :					T ):


       """simple docstring"""







       if node not in self.connections:
          UpperCamelCase					=  {}






    def  A       (  self      :					int  ,						UpperCamelCase__      :					T  ,						UpperCamelCase__      :					T  ,						UpperCamelCase__      :					int ):


       """simple docstring"""







       self.add_node(_lowerCamelCase )
       self.add_node(_lowerCamelCase )
       UpperCamelCase					=  weight
       UpperCamelCase					=  weight






    def  A       (  self      :					Any ):


       """simple docstring"""







       UpperCamelCase					=  []
       UpperCamelCase					=  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 UpperCamelCase__ : x[2] )

       # creating the disjoint set
       UpperCamelCase					=  DisjointSetTree[T]()
       for node in self.connections:
          disjoint_set.make_set(_lowerCamelCase )

       # MST generation
       UpperCamelCase					=  0
       UpperCamelCase					=  0
       UpperCamelCase					=  GraphUndirectedWeighted[T]()
       while num_edges < len(self.connections ) - 1:
          UpperCamelCase				,      UpperCamelCase				,      UpperCamelCase					=  edges[index]
          index += 1
          UpperCamelCase					=  disjoint_set.find_set(_lowerCamelCase )
          UpperCamelCase					=  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"""


import re



def 					lowerCAmelCase				(    __UpperCamelCase ):




  """simple docstring"""







  return [char.split() for char in re.split(r'''[^ a-z A-Z 0-9 \s]'''		,       str_ )]



def 					lowerCAmelCase				(    __UpperCamelCase ):




  """simple docstring"""







  __A									= split_input(str_ )
  return "".join(
      [''''''.join([char.capitalize() for char in sub_str] ) for sub_str in string_split] )



def 					lowerCAmelCase				(    __UpperCamelCase		,       __UpperCamelCase		,       __UpperCamelCase ):




  """simple docstring"""







  try:
    __A									= split_input(__UpperCamelCase )
    if upper:
      __A									= ''''''.join(
          [
              separator.join([char.upper() for char in sub_str] )
              for sub_str in string_split
          ] )
    else:
      __A									= ''''''.join(
          [
              separator.join([char.lower() for char in sub_str] )
              for sub_str in string_split
          ] )
    return res_str
  except IndexError:
    return "not valid string"



def 					lowerCAmelCase				(    __UpperCamelCase ):




  """simple docstring"""







  return to_simple_case(__UpperCamelCase )



def 					lowerCAmelCase				(    __UpperCamelCase ):




  """simple docstring"""







  try:
    __A									= to_simple_case(__UpperCamelCase )
    return res_str[0].lower() + res_str[1:]
  except IndexError:
    return "not valid string"



def 					lowerCAmelCase				(    __UpperCamelCase		,       __UpperCamelCase ):




  """simple docstring"""







  return to_complex_case(__UpperCamelCase		,       __UpperCamelCase		,       '''_''' )



def 					lowerCAmelCase				(    __UpperCamelCase		,       __UpperCamelCase ):




  """simple docstring"""







  return to_complex_case(__UpperCamelCase		,       __UpperCamelCase		,       '''-''' )


if __name__ == "__main__":
       __import__('doctest').testmod()




