

"""simple docstring"""





class  _lowerCAmelCase  (     _A       ):







 """simple docstring"""







 pass







class  _lowerCAmelCase  (     _A       ):







 """simple docstring"""







 pass







class  _lowerCAmelCase  :







 """simple docstring"""







 def __init__(      self							:      Tuple     ):
    __lowercase								=						[
        [],
        [],
        [],
    ]


 def  _lowercase			(      self							:      Union[str, Any], UpperCAmelCase__							:      int, UpperCAmelCase__							:      int     ):
    try:
       if len(self.queues[priority]     ) >= 1_0_0:
          raise OverflowError("Maximum queue size is 100"     )
       self.queues[priority].append(__SCREAMING_SNAKE_CASE     )
    except IndexError:
       raise ValueError("Valid priorities are 0, 1, and 2"     )


 def  _lowercase			(      self							:      List[str]     ):
    for queue in self.queues:
       if queue:
          return queue.pop(0     )
    raise UnderFlowError("All queues are empty"     )



 def __str__(      self							:      Any     ):
    return "\n".join(F"""Priority {i}: {q}""" for i, q in enumerate(self.queues     )     )







class  _lowerCAmelCase  :







 """simple docstring"""







 def __init__(      self							:      Optional[Any]     ):
    __lowercase								=						[]


 def  _lowercase			(      self							:      Union[str, Any], UpperCAmelCase__							:      int     ):
    if len(self.queue     ) == 1_0_0:
       raise OverFlowError("Maximum queue size is 100"     )
    self.queue.append(__SCREAMING_SNAKE_CASE     )


 def  _lowercase			(      self							:      Dict     ):
    if not self.queue:
       raise UnderFlowError("The queue is empty"     )
    else:
       __lowercase								=						min(self.queue     )
       self.queue.remove(__SCREAMING_SNAKE_CASE     )
       return data



 def __str__(      self							:      List[str]     ):
    return str(self.queue     )







def   _A  (  )     ->						Any:
   '''simple docstring'''


   __lowercase								=						FixedPriorityQueue()
   fpq.enqueue(0,      10)
   fpq.enqueue(1,      70)
   fpq.enqueue(0,      100)
   fpq.enqueue(2,      1)
   fpq.enqueue(2,      5)
   fpq.enqueue(1,      7)
   fpq.enqueue(2,      4)
   fpq.enqueue(1,      64)
   fpq.enqueue(0,      128)
   print(lowercase__)
   print(fpq.dequeue())
   print(fpq.dequeue())
   print(fpq.dequeue())
   print(fpq.dequeue())
   print(fpq.dequeue())
   print(lowercase__)
   print(fpq.dequeue())
   print(fpq.dequeue())
   print(fpq.dequeue())
   print(fpq.dequeue())
   print(fpq.dequeue())




def   _A  (  )     ->						Optional[Any]:
   '''simple docstring'''


   __lowercase								=						ElementPriorityQueue()
   epq.enqueue(10)
   epq.enqueue(70)
   epq.enqueue(100)
   epq.enqueue(1)
   epq.enqueue(5)
   epq.enqueue(7)
   epq.enqueue(4)
   epq.enqueue(64)
   epq.enqueue(128)
   print(lowercase__)
   print(epq.dequeue())
   print(epq.dequeue())
   print(epq.dequeue())
   print(epq.dequeue())
   print(epq.dequeue())
   print(lowercase__)
   print(epq.dequeue())
   print(epq.dequeue())
   print(epq.dequeue())
   print(epq.dequeue())
   print(epq.dequeue())


if __name__ == "__main__":
   fixed_priority_queue()
   element_priority_queue()







"""simple docstring"""





from __future__ import annotations

from typing import Any




class  _lowerCAmelCase  :







 """simple docstring"""







 def __init__(      self							:      Union[str, Any], UpperCAmelCase__							:      int     ):
    __lowercase								=						num_of_nodes
    __lowercase								=						[]
    __lowercase								=						{}


 def  _lowercase			(      self							:      Tuple, UpperCAmelCase__							:      int, UpperCAmelCase__							:      int, UpperCAmelCase__							:      int     ):
    self.m_edges.append([u_node, v_node, weight]     )


 def  _lowercase			(      self							:      Dict, UpperCAmelCase__							:      int     ):

    if self.m_component[u_node] == u_node:
       return u_node
    return self.find_component(self.m_component[u_node]     )


 def  _lowercase			(      self							:      Dict, UpperCAmelCase__							:      int     ):

    if self.m_component[u_node] != u_node:
       for k in self.m_component:
          __lowercase								=						self.find_component(UpperCAmelCase__     )


 def  _lowercase			(      self							:      str, UpperCAmelCase__							:      list[int], UpperCAmelCase__							:      int, UpperCAmelCase__							:      int     ):

    if component_size[u_node] <= component_size[v_node]:
       __lowercase								=						v_node
       component_size[v_node] += component_size[u_node]
       self.set_component(UpperCAmelCase__     )

    elif component_size[u_node] >= component_size[v_node]:
       __lowercase								=						self.find_component(UpperCAmelCase__     )
       component_size[u_node] += component_size[v_node]
       self.set_component(UpperCAmelCase__     )



 def  _lowercase			(      self							:      Tuple     ):
    __lowercase								=						[]
    __lowercase								=						0

    __lowercase								=						[-1] * self.m_num_of_nodes

    # A list of components (initialized to all of the nodes)
    for node in range(self.m_num_of_nodes     ):
       self.m_component.update({node: node}     )
       component_size.append(1     )

    __lowercase								=						self.m_num_of_nodes

    while num_of_components > 1:
       for edge in self.m_edges:
          __lowercase		,__lowercase		,__lowercase								=						edge

          __lowercase								=						self.m_component[u]
          __lowercase								=						self.m_component[v]

          if u_component != v_component:

             for component in (u_component, v_component):
                if (
                    minimum_weight_edge[component] == -1
                    or minimum_weight_edge[component][2] > w
                ):
                   __lowercase								=						[u, v, w]

       for edge in minimum_weight_edge:
          if isinstance(UpperCAmelCase__, UpperCAmelCase__     ):
             __lowercase		,__lowercase		,__lowercase								=						edge

             __lowercase								=						self.m_component[u]
             __lowercase								=						self.m_component[v]

             if u_component != v_component:
                mst_weight += w
                self.union(UpperCAmelCase__, UpperCAmelCase__, UpperCAmelCase__     )
                print(F"""Added edge [{u} - {v}]\nAdded weight: {w}\n"""     )
                num_of_components -= 1

       __lowercase								=						[-1] * self.m_num_of_nodes
    print(F"""The total weight of the minimal spanning tree is: {mst_weight}"""     )







def   _A  (  )     ->						None:
   '''simple docstring'''




if __name__ == "__main__":
   import doctest

   doctest.testmod()




