




'''simple docstring'''





from __future__ import annotations

from typing import Generic, TypeVar

_SCREAMING_SNAKE_CASE							:       Tuple						=			TypeVar("T")




class 			_snake_case		(     Generic[T]							):




			def __init__( self    ,							a__							)    ->    None:

										'''simple docstring'''




										snake_case_      =				data
										snake_case_      =				self
										snake_case_      =				0




class 			_snake_case		(     Generic[T]							):




			def __init__( self							)    ->    None:

										'''simple docstring'''




										snake_case_      =				{}




			def        lowerCAmelCase__    ( self    ,							a__							)    ->    None:

										'''simple docstring'''




										snake_case_      =				DisjointSetTreeNode(a__							)




			def        lowerCAmelCase__    ( self    ,							a__							)    ->    DisjointSetTreeNode[T]:

										'''simple docstring'''




										snake_case_      =				self.map[data]
										if elem_ref != elem_ref.parent:
																	snake_case_      =				self.find_set(elem_ref.parent.data							)
										return elem_ref.parent




			def        lowerCAmelCase__    ( self    ,							a__    ,							a__							)    ->    None:

										'''simple docstring'''




										if nodea.rank > nodea.rank:
																	snake_case_      =				nodea
										else:
																	snake_case_      =				nodea
																	if nodea.rank == nodea.rank:
																								nodea.rank += 1




			def        lowerCAmelCase__    ( self    ,							a__    ,							a__							)    ->    None:

										'''simple docstring'''




										self.link(self.find_set(a__							)    ,							self.find_set(a__							)							)




class 			_snake_case		(     Generic[T]							):




			def __init__( self							)    ->    None:

										'''simple docstring'''




										snake_case_      =				{}




			def        lowerCAmelCase__    ( self    ,							a__							)    ->    None:

										'''simple docstring'''




										if node not in self.connections:
																	snake_case_      =				{}




			def        lowerCAmelCase__    ( self    ,							a__    ,							a__    ,							a__							)    ->    None:

										'''simple docstring'''




										self.add_node(a__							)
										self.add_node(a__							)
										snake_case_      =				weight
										snake_case_      =				weight




			def        lowerCAmelCase__    ( self							)    ->    GraphUndirectedWeighted[T]:

										'''simple docstring'''




										snake_case_      =				[]
										snake_case_      =				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 a__							: x[2]							)

										# creating the disjoint set
										snake_case_      =				DisjointSetTree[T]()
										for node in self.connections:
																	disjoint_set.make_set(a__							)

										# MST generation
										snake_case_      =				0
										snake_case_      =				0
										snake_case_      =				GraphUndirectedWeighted[T]()
										while num_edges < len(self.connections							) - 1:
																	snake_case_ ,				snake_case_ ,				snake_case_      =				edges[index]
																	index += 1
																	snake_case_      =				disjoint_set.find_set(a__							)
																	snake_case_      =				disjoint_set.find_set(a__							)
																	if parent_u != parent_v:
																								num_edges += 1
																								graph.add_edge(a__    ,							a__    ,							a__							)
																								disjoint_set.union(a__    ,							a__							)
										return graph










'''simple docstring'''





def 					UpperCamelCase_(     snake_case							:	int							,    snake_case							:	int					):

							'''simple docstring'''






							while b:
														snake_case_ ,				snake_case_      =				b, a % b
							return a


def 					UpperCamelCase_(     snake_case							:	int							,    snake_case							:	int					):

							'''simple docstring'''






							return a if b == 0 else euclidean_gcd_recursive(snake_case							,    a % b					)


def 					UpperCamelCase_(     ):

							'''simple docstring'''






							print(f'euclidean_gcd(3, 5) = {euclidean_gcd(3							,    5					)}'					)
							print(f'euclidean_gcd(5, 3) = {euclidean_gcd(5							,    3					)}'					)
							print(f'euclidean_gcd(1, 3) = {euclidean_gcd(1							,    3					)}'					)
							print(f'euclidean_gcd(3, 6) = {euclidean_gcd(3							,    6					)}'					)
							print(f'euclidean_gcd(6, 3) = {euclidean_gcd(6							,    3					)}'					)

							print(f'euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3							,    5					)}'					)
							print(f'euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5							,    3					)}'					)
							print(f'euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1							,    3					)}'					)
							print(f'euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3							,    6					)}'					)
							print(f'euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6							,    3					)}'					)


if __name__ == "__main__":
		main()




