'''simple docstring'''

from __future__ import annotations

from typing import Any





class 							lowercase						:


   def __init__(   self				:	List[Any]   ,		__lowerCAmelCase				:	int)      ->					None:
         lowercase_     =      num_of_nodes
         lowercase_     =      []
         lowercase_     =      {}


   def __UpperCAmelCase       (   self				:	List[str]   ,		__lowerCAmelCase				:	int   ,		__lowerCAmelCase				:	int   ,		__lowerCAmelCase				:	int)      ->					None:
         self.m_edges.append([u_node, v_node, weight])


   def __UpperCAmelCase       (   self				:	Union[str, Any]   ,		__lowerCAmelCase				:	int)      ->					int:

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


   def __UpperCAmelCase       (   self				:	Optional[Any]   ,		__lowerCAmelCase				:	int)      ->					None:

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


   def __UpperCAmelCase       (   self				:	int   ,		__lowerCAmelCase				:	list[int]   ,		__lowerCAmelCase				:	int   ,		__lowerCAmelCase				:	int)      ->					None:

         if component_size[u_node] <= component_size[v_node]:
               lowercase_     =      v_node
               component_size[v_node] += component_size[u_node]
               self.set_component(__lowerCAmelCase)

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


   def __UpperCAmelCase       (   self				:	Optional[int])      ->					None:
         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(__lowerCAmelCase   ,		__lowerCAmelCase):
                           lowercase_ ,							lowercase_ ,							lowercase_     =      edge

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

                           if u_component != v_component:
                                 mst_weight += w
                                 self.union(__lowerCAmelCase   ,		__lowerCAmelCase   ,		__lowerCAmelCase)
                                 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()







'''simple docstring'''

def __a (	__lowerCamelCase			:						int = 200				)	->							int:
      '''simple docstring'''


      lowercase_     =      [1, 2, 5, 10, 20, 50, 100, 200]
      lowercase_     =      [0] * (pence + 1)
      lowercase_     =      1  # base case: 1 way to make 0 pence

      for coin in coins:
            for i in range(__lowerCamelCase ,		pence + 1 ,		1				):
                  number_of_ways[i] += number_of_ways[i - coin]
      return number_of_ways[pence]


if __name__ == "__main__":
       assert solution(200) == 73_682






