
"""simple docstring"""


from __future__ import annotations

from typing import Generic, TypeVar

SCREAMING_SNAKE_CASE      =     TypeVar("""T""")



class   __a  (      Generic[T]	):






       def __init__(  self :							List[Any]       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              UpperCamelCase					 =		data
              UpperCamelCase					 =		self
              UpperCamelCase					 =		0





class   __a  (      Generic[T]	):






       def __init__(  self :							int			)->  None:







              """simple docstring"""
              # map from node name to the node object
              UpperCamelCase					 =		{}






       def 	_SCREAMING_SNAKE_CASE       (  self :							Optional[int]       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              # create a new set with x as its member
              UpperCamelCase					 =		DisjointSetTreeNode(UpperCAmelCase_			)






       def 	_SCREAMING_SNAKE_CASE       (  self :							Optional[Any]       ,      UpperCAmelCase_ :							T			)->  DisjointSetTreeNode[T]:







              """simple docstring"""
              # find the set x belongs to (with path-compression)
              UpperCamelCase					 =		self.map[data]
              if elem_ref != elem_ref.parent:
                     UpperCamelCase					 =		self.find_set(elem_ref.parent.data			)
              return elem_ref.parent






       def 	_SCREAMING_SNAKE_CASE       (  self :							Any       ,      UpperCAmelCase_ :							DisjointSetTreeNode[T]       ,      UpperCAmelCase_ :							DisjointSetTreeNode[T]			)->  None:







              """simple docstring"""
              # helper function for union operation
              if nodea.rank > nodea.rank:
                     UpperCamelCase					 =		nodea
              else:
                     UpperCamelCase					 =		nodea
                     if nodea.rank == nodea.rank:
                            nodea.rank += 1






       def 	_SCREAMING_SNAKE_CASE       (  self :							int       ,      UpperCAmelCase_ :							T       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              # merge 2 disjoint sets
              self.link(self.find_set(UpperCAmelCase_			)       ,      self.find_set(UpperCAmelCase_			)			)





class   __a  (      Generic[T]	):






       def __init__(  self :							Dict			)->  None:







              """simple docstring"""
              # connections: map from the node to the neighbouring nodes (with weights)
              UpperCamelCase					 =		{}






       def 	_SCREAMING_SNAKE_CASE       (  self :							Any       ,      UpperCAmelCase_ :							T			)->  None:







              """simple docstring"""
              # add a node ONLY if its not present in the graph
              if node not in self.connections:
                     UpperCamelCase					 =		{}






       def 	_SCREAMING_SNAKE_CASE       (  self :							Optional[Any]       ,      UpperCAmelCase_ :							T       ,      UpperCAmelCase_ :							T       ,      UpperCAmelCase_ :							int			)->  None:







              """simple docstring"""
              # add an edge with the given weight
              self.add_node(UpperCAmelCase_			)
              self.add_node(UpperCAmelCase_			)
              UpperCamelCase					 =		weight
              UpperCamelCase					 =		weight






       def 	_SCREAMING_SNAKE_CASE       (  self :							Tuple			)->  GraphUndirectedWeighted[T]:







              """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(UpperCAmelCase_			)

              # 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(UpperCAmelCase_			)
                     UpperCamelCase					 =		disjoint_set.find_set(UpperCAmelCase_			)
                     if parent_u != parent_v:
                            num_edges += 1
                            graph.add_edge(UpperCAmelCase_       ,      UpperCAmelCase_       ,      UpperCAmelCase_			)
                            disjoint_set.union(UpperCAmelCase_       ,      UpperCAmelCase_			)
              return graph







"""simple docstring"""


def 	lowerCamelCase__			(							UpperCAmelCase_				)->							int:







       """simple docstring"""
       if a < 0:
              raise ValueError("Input value must be a positive integer"				)
       elif isinstance(UpperCAmelCase_		,      UpperCAmelCase_				):
              raise TypeError("Input value must be a 'int' type"				)
       return bin(UpperCAmelCase_				).count("1"				)


if __name__ == "__main__":
      import doctest

      doctest.testmod()





