
from __future__ import annotations

from typing import Any




class 			UpperCAmelCase_     :


  '''simple docstring'''







  def __init__(					self     :					Optional[Any]     ,				UpperCamelCase__     :					int       )     ->      None:







    """simple docstring"""






    __magic_name__								=			num_of_nodes
    __magic_name__								=			[]
    __magic_name__								=			{}
  def 				_lowercase				(					self     :					int     ,				UpperCamelCase__     :					int     ,				UpperCamelCase__     :					int     ,				UpperCamelCase__     :					int       )     ->      None:







    """simple docstring"""






    self.m_edges.append([u_node, v_node, weight]       )
  def 				_lowercase				(					self     :					List[Any]     ,				UpperCamelCase__     :					int       )     ->      int:







    """simple docstring"""






    if self.m_component[u_node] == u_node:
      return u_node
    return self.find_component(self.m_component[u_node]       )
  def 				_lowercase				(					self     :					Optional[int]     ,				UpperCamelCase__     :					int       )     ->      None:







    """simple docstring"""






    if self.m_component[u_node] != u_node:
      for k in self.m_component:
        __magic_name__								=			self.find_component(UpperCamelCase__       )
  def 				_lowercase				(					self     :					str     ,				UpperCamelCase__     :					list[int]     ,				UpperCamelCase__     :					int     ,				UpperCamelCase__     :					int       )     ->      None:







    """simple docstring"""






    if component_size[u_node] <= component_size[v_node]:
      __magic_name__								=			v_node
      component_size[v_node] += component_size[u_node]
      self.set_component(UpperCamelCase__       )

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





  def 				_lowercase				(					self     :					int       )     ->      None:







    """simple docstring"""






    __magic_name__								=			[]
    __magic_name__								=			0

    __magic_name__								=			[-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       )

    __magic_name__								=			self.m_num_of_nodes

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

        __magic_name__								=			self.m_component[u]
        __magic_name__								=			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
            ):
              __magic_name__								=			[u, v, w]

      for edge in minimum_weight_edge:
        if isinstance(UpperCamelCase__     ,				UpperCamelCase__       ):
          __magic_name__	,       __magic_name__	,       __magic_name__								=			edge

          __magic_name__								=			self.m_component[u]
          __magic_name__								=			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

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







def a__       (			):






  '''simple docstring'''







if __name__ == "__main__":
    import doctest

    doctest.testmod()



from maths.is_square_free import is_square_free
from maths.prime_factors import prime_factors

def a__       (			A_   ):






  '''simple docstring'''





  __magic_name__								=			prime_factors(A_   )
  if is_square_free(A_   ):
    return -1 if len(A_   ) % 2 else 1
  return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()

