
"""simple docstring"""







# Author: OMKAR PATHAK, Nwachukwu Chidiebere

# Use a Python dictionary to construct the graph.
from __future__ import annotations

from pprint import pformat
from typing import Generic, TypeVar

lowerCamelCase__   					=		TypeVar("""T""")




class  A__       (	Generic[T]):

		def __init__(      self       ,		_SCREAMING_SNAKE_CASE = True ):
			__lowerCAmelCase			:						dict[T, list[T]]									=      {}  # dictionary of lists
			__lowerCAmelCase			:						Optional[int]									=      directed

		def 							__lowerCamelCase							(      self       ,		_SCREAMING_SNAKE_CASE       ,		_SCREAMING_SNAKE_CASE ):

			if not self.directed:  # For undirected graphs
				# if both source vertex and destination vertex are both present in the
				# adjacency list, add destination vertex to source vertex list of adjacent
				# vertices and add source vertex to destination vertex list of adjacent
				# vertices.
				if source_vertex in self.adj_list and destination_vertex in self.adj_list:
					self.adj_list[source_vertex].append(_SCREAMING_SNAKE_CASE )
					self.adj_list[destination_vertex].append(_SCREAMING_SNAKE_CASE )
				# if only source vertex is present in adjacency list, add destination vertex
				# to source vertex list of adjacent vertices, then create a new vertex with
				# destination vertex as key and assign a list containing the source vertex
				# as it's first adjacent vertex.
				elif source_vertex in self.adj_list:
					self.adj_list[source_vertex].append(_SCREAMING_SNAKE_CASE )
					__lowerCAmelCase			:						str									=      [source_vertex]
				# if only destination vertex is present in adjacency list, add source vertex
				# to destination vertex list of adjacent vertices, then create a new vertex
				# with source vertex as key and assign a list containing the source vertex
				# as it's first adjacent vertex.
				elif destination_vertex in self.adj_list:
					self.adj_list[destination_vertex].append(_SCREAMING_SNAKE_CASE )
					__lowerCAmelCase			:						Dict									=      [destination_vertex]
				# if both source vertex and destination vertex are not present in adjacency
				# list, create a new vertex with source vertex as key and assign a list
				# containing the destination vertex as it's first adjacent vertex also
				# create a new vertex with destination vertex as key and assign a list
				# containing the source vertex as it's first adjacent vertex.
				else:
					__lowerCAmelCase			:						str									=      [destination_vertex]
					__lowerCAmelCase			:						Optional[int]									=      [source_vertex]
			else:  # For directed graphs
				# if both source vertex and destination vertex are present in adjacency
				# list, add destination vertex to source vertex list of adjacent vertices.
				if source_vertex in self.adj_list and destination_vertex in self.adj_list:
					self.adj_list[source_vertex].append(_SCREAMING_SNAKE_CASE )
				# if only source vertex is present in adjacency list, add destination
				# vertex to source vertex list of adjacent vertices and create a new vertex
				# with destination vertex as key, which has no adjacent vertex
				elif source_vertex in self.adj_list:
					self.adj_list[source_vertex].append(_SCREAMING_SNAKE_CASE )
					__lowerCAmelCase			:						Tuple									=      []
				# if only destination vertex is present in adjacency list, create a new
				# vertex with source vertex as key and assign a list containing destination
				# vertex as first adjacent vertex
				elif destination_vertex in self.adj_list:
					__lowerCAmelCase			:						Any									=      [destination_vertex]
				# if both source vertex and destination vertex are not present in adjacency
				# list, create a new vertex with source vertex as key and a list containing
				# destination vertex as it's first adjacent vertex. Then create a new vertex
				# with destination vertex as key, which has no adjacent vertex
				else:
					__lowerCAmelCase			:						str									=      [destination_vertex]
					__lowerCAmelCase			:						int									=      []

			return self







		def __repr__(      self ):
			return pformat(self.adj_list )
"""simple docstring"""




from __future__ import annotations

from typing import Generic, TypeVar

__lowerCamelCase							 =     TypeVar("T")
class 			UpperCamelCase__(	Generic[T]       ):





						def __init__(				self						,__UpperCAmelCase   )    -> None:
													A__		   =							data
													A__		   =							self
													A__		   =							0






class 			UpperCamelCase__(	Generic[T]       ):





						def __init__(				self   )    -> None:
													# map from node name to the node object
													A__		   =							{}





						def  snake_case__		(				self						,__UpperCAmelCase   )    -> None:
													# create a new set with x as its member
													A__		   =							DisjointSetTreeNode(__UpperCAmelCase   )





						def  snake_case__		(				self						,__UpperCAmelCase   )    -> DisjointSetTreeNode[T]:
													# find the set x belongs to (with path-compression)
													A__		   =							self.map[data]
													if elem_ref != elem_ref.parent:
																				A__		   =							self.find_set(elem_ref.parent.data   )
													return elem_ref.parent





						def  snake_case__		(				self						,__UpperCAmelCase						,__UpperCAmelCase   )    -> None:
													# helper function for union operation
													if nodea.rank > nodea.rank:
																				A__		   =							nodea
													else:
																				A__		   =							nodea
																				if nodea.rank == nodea.rank:
																											nodea.rank += 1





						def  snake_case__		(				self						,__UpperCAmelCase						,__UpperCAmelCase   )    -> None:
													# merge 2 disjoint sets
													self.link(self.find_set(__UpperCAmelCase   )						,self.find_set(__UpperCAmelCase   )   )






class 			UpperCamelCase__(	Generic[T]       ):





						def __init__(				self   )    -> None:
													# connections: map from the node to the neighbouring nodes (with weights)
													A__		   =							{}





						def  snake_case__		(				self						,__UpperCAmelCase   )    -> None:
													# add a node ONLY if its not present in the graph
													if node not in self.connections:
																				A__		   =							{}





						def  snake_case__		(				self						,__UpperCAmelCase						,__UpperCAmelCase						,__UpperCAmelCase   )    -> None:
													# add an edge with the given weight
													self.add_node(__UpperCAmelCase   )
													self.add_node(__UpperCAmelCase   )
													A__		   =							weight
													A__		   =							weight





						def  snake_case__		(				self   )    -> GraphUndirectedWeighted[T]:
													A__		   =							[]
													A__		   =							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
													A__		   =							DisjointSetTree[T]()
													for node in self.connections:
																				disjoint_set.make_set(__UpperCAmelCase   )

													# MST generation
													A__		   =							0
													A__		   =							0
													A__		   =							GraphUndirectedWeighted[T]()
													while num_edges < len(self.connections   ) - 1:
																				A__   ,     A__   ,     A__		   =							edges[index]
																				index += 1
																				A__		   =							disjoint_set.find_set(__UpperCAmelCase   )
																				A__		   =							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





