





"""simple docstring"""




from __future__ import annotations

from typing import Generic, TypeVar

_snake_case           =			TypeVar("""T""")





class  lowerCAmelCase							(       Generic[T] ):







  def __init__(      self  :int   ,							_lowercase  :T ):






     '''simple docstring'''





     lowercase__			       =  data
     lowercase__			       =  self
     lowercase__			       =  0





class  lowerCAmelCase							(       Generic[T] ):







  def __init__(      self  :Union[str, Any] ):






     '''simple docstring'''





     lowercase__			       =  {}







  def   UpperCAmelCase					(      self  :int   ,							_lowercase  :T ):






     '''simple docstring'''





     lowercase__			       =  DisjointSetTreeNode(_lowercase )







  def   UpperCAmelCase					(      self  :List[str]   ,							_lowercase  :T ):






     '''simple docstring'''





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







  def   UpperCAmelCase					(      self  :str   ,							_lowercase  :DisjointSetTreeNode[T]   ,							_lowercase  :DisjointSetTreeNode[T] ):






     '''simple docstring'''





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







  def   UpperCAmelCase					(      self  :Dict   ,							_lowercase  :T   ,							_lowercase  :T ):






     '''simple docstring'''





     self.link(self.find_set(_lowercase )   ,							self.find_set(_lowercase ) )





class  lowerCAmelCase							(       Generic[T] ):







  def __init__(      self  :str ):






     '''simple docstring'''





     lowercase__			       =  {}







  def   UpperCAmelCase					(      self  :str   ,							_lowercase  :T ):






     '''simple docstring'''





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







  def   UpperCAmelCase					(      self  :Optional[int]   ,							_lowercase  :T   ,							_lowercase  :T   ,							_lowercase  :int ):






     '''simple docstring'''





     self.add_node(_lowercase )
     self.add_node(_lowercase )
     lowercase__			       =  weight
     lowercase__			       =  weight







  def   UpperCAmelCase					(      self  :List[Any] ):






     '''simple docstring'''





     lowercase__			       =  []
     lowercase__			       =  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 _lowercase : x[2] )

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

     # MST generation
     lowercase__			       =  0
     lowercase__			       =  0
     lowercase__			       =  GraphUndirectedWeighted[T]()
     while num_edges < len(self.connections ) - 1:
        lowercase__       ,							lowercase__       ,							lowercase__			       =  edges[index]
        index += 1
        lowercase__			       =  disjoint_set.find_set(_lowercase )
        lowercase__			       =  disjoint_set.find_set(_lowercase )
        if parent_u != parent_v:
           num_edges += 1
           graph.add_edge(_lowercase   ,							_lowercase   ,							_lowercase )
           disjoint_set.union(_lowercase   ,							_lowercase )
     return graph













from __future__ import annotations


def _A       (   __magic_name__  , __magic_name__	):
   lowercase__			       =  0
   lowercase__			       =  len(__magic_name__	) - 1

   while i < j:
      if nums[i] + nums[j] == target:
         return [i, j]
      elif nums[i] + nums[j] < target:
         lowercase__			       =  i + 1
      else:
         lowercase__			       =  j - 1

   return []


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  print(F"""{two_pointer([2, 7, 11, 15], 9) = }""")






