class      __lowercase					:

						def __init__(	self				:      Dict   )							->		int:


									'''simple docstring'''

									lowercase							=		0
									lowercase							=		0
									lowercase							=		{}

						def        __a		(	self				:      Union[str, Any]							,							__lowerCamelCase				:      int   )							->		Union[str, Any]:


									'''simple docstring'''

									if vertex not in self.adjacency:
												lowercase							=		{}
												self.num_vertices += 1

						def        __a		(	self				:      Optional[int]							,							__lowerCamelCase				:      Union[str, Any]							,							__lowerCamelCase				:      Tuple							,							__lowerCamelCase				:      str   )							->		List[Any]:


									'''simple docstring'''

									self.add_vertex(__lowerCamelCase   )
									self.add_vertex(__lowerCamelCase   )

									if head == tail:
												return

									lowercase							=		weight
									lowercase							=		weight

						def        __a		(	self				:      str   )							->		Tuple:


									'''simple docstring'''

									lowercase							=		self.get_edges()
									for edge in edges:
												lowercase		,lowercase		,lowercase							=		edge
												edges.remove((tail, head, weight)   )
									for i in range(len(__lowerCamelCase   )   ):
												lowercase							=		list(edges[i]   )

									edges.sort(key=lambda __lowerCamelCase   : e[2]   )
									for i in range(len(__lowerCamelCase   ) - 1   ):
												if edges[i][2] >= edges[i + 1][2]:
															lowercase							=		edges[i][2] + 1
									for edge in edges:
												lowercase		,lowercase		,lowercase							=		edge
												lowercase							=		weight
												lowercase							=		weight

						def __str__(	self				:      Tuple   )							->		Union[str, Any]:


									'''simple docstring'''

									lowercase							=		''''''
									for tail in self.adjacency:
												for head in self.adjacency[tail]:
															lowercase							=		self.adjacency[head][tail]
															string += f'{head} -> {tail} == {weight}\n'
									return string.rstrip('''\n'''   )

						def        __a		(	self				:      Optional[int]   )							->		List[str]:


									'''simple docstring'''

									lowercase							=		[]
									for tail in self.adjacency:
												for head in self.adjacency[tail]:
															output.append((tail, head, self.adjacency[head][tail])   )
									return output

						def        __a		(	self				:      Dict   )							->		Optional[int]:


									'''simple docstring'''

									return self.adjacency.keys()

						@staticmethod
						def        __a		(	__lowerCamelCase				:      str=None							,							__lowerCamelCase				:      Tuple=None   )							->		Union[str, Any]:


									'''simple docstring'''

									lowercase							=		Graph()
									if vertices is None:
												lowercase							=		[]
									if edges is None:
												lowercase							=		[]
									for vertex in vertices:
												g.add_vertex(__lowerCamelCase   )
									for edge in edges:
												g.add_edge(*__lowerCamelCase   )
									return g






						class      __lowercase					:

												def __init__(	self				:      Optional[Any]   )							->		str:


															'''simple docstring'''

															lowercase							=		{}
															lowercase							=		{}

												def __len__(	self				:      Any   )							->		str:


															'''simple docstring'''

															return len(self.parent   )

												def        __a		(	self				:      Optional[int]							,							__lowerCamelCase				:      Union[str, Any]   )							->		Any:


															'''simple docstring'''

															if item in self.parent:
																		return self.find(__lowerCamelCase   )

															lowercase							=		item
															lowercase							=		0
															return item

												def        __a		(	self				:      Optional[int]							,							__lowerCamelCase				:      Dict   )							->		Optional[int]:


															'''simple docstring'''

															if item not in self.parent:
																		return self.make_set(__lowerCamelCase   )
															if item != self.parent[item]:
																		lowercase							=		self.find(self.parent[item]   )
															return self.parent[item]



												def        __a		(	self				:      List[str]							,							__lowerCamelCase				:      Any							,							__lowerCamelCase				:      Tuple   )							->		int:


															'''simple docstring'''

															lowercase							=		self.find(__lowerCamelCase   )
															lowercase							=		self.find(__lowerCamelCase   )

															if roota == roota:
																		return roota

															if self.rank[roota] > self.rank[roota]:
																		lowercase							=		roota
																		return roota

															if self.rank[roota] < self.rank[roota]:
																		lowercase							=		roota
																		return roota

															if self.rank[roota] == self.rank[roota]:
																		self.rank[roota] += 1
																		lowercase							=		roota
																		return roota
															return None





						@staticmethod
						def        __a		(	__lowerCamelCase				:      str   )							->		int:


									'''simple docstring'''

									lowercase							=		graph.num_vertices

									lowercase							=		Graph.UnionFind()
									lowercase							=		[]
									while num_components > 1:
												lowercase							=		{}
												for vertex in graph.get_vertices():
															lowercase							=		-1

												lowercase							=		graph.get_edges()
												for edge in edges:
															lowercase		,lowercase		,lowercase							=		edge
															edges.remove((tail, head, weight)   )
												for edge in edges:
															lowercase		,lowercase		,lowercase							=		edge
															lowercase							=		union_find.find(__lowerCamelCase   )
															lowercase							=		union_find.find(__lowerCamelCase   )
															if seta != seta:
																		if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																					lowercase							=		[head, tail, weight]

																		if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																					lowercase							=		[head, tail, weight]
												for vertex in cheap_edge:
															if cheap_edge[vertex] != -1:
																		lowercase		,lowercase		,lowercase							=		cheap_edge[vertex]
																		if union_find.find(__lowerCamelCase   ) != union_find.find(__lowerCamelCase   ):
																					union_find.union(__lowerCamelCase							,							__lowerCamelCase   )
																					mst_edges.append(cheap_edge[vertex]   )
																					lowercase							=		num_components - 1
									lowercase							=		Graph.build(edges=__lowerCamelCase   )
									return mst






from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

A_      =      TypeVar("KEY")
A_      =      TypeVar("VAL")






@dataclass(frozen=_A       ,     slots=_A    )
class      __lowercase					(    Generic[KEY, VAL]    ):
						lowercase					 =     42
						lowercase					 =     42






class      __lowercase					(    _Item    ):

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


									'''simple docstring'''

									super().__init__(__lowerCamelCase							,							__lowerCamelCase   )



						def __bool__(	self				:      str   )							->		bool:


									'''simple docstring'''

									return False





A_      =      _DeletedItem()






class      __lowercase					(    MutableMapping[KEY, VAL]    ):

						def __init__(	self				:      Any							,							__lowerCamelCase				:      int = 8							,							__lowerCamelCase				:      float = 0.75   )							->		None:


									'''simple docstring'''

									lowercase							=		initial_block_size
									lowercase							=		[None] * initial_block_size
									assert 0.0 < capacity_factor < 1.0
									lowercase							=		capacity_factor
									lowercase							=		0

						def        __a		(	self				:      Optional[Any]							,							__lowerCamelCase				:      KEY   )							->		int:


									'''simple docstring'''

									return hash(__lowerCamelCase   ) % len(self._buckets   )

						def        __a		(	self				:      List[Any]							,							__lowerCamelCase				:      int   )							->		int:


									'''simple docstring'''

									return (ind + 1) % len(self._buckets   )

						def        __a		(	self				:      Optional[Any]							,							__lowerCamelCase				:      int							,							__lowerCamelCase				:      KEY							,							__lowerCamelCase				:      VAL   )							->		bool:


									'''simple docstring'''

									lowercase							=		self._buckets[ind]
									if not stored:
												lowercase							=		_Item(__lowerCamelCase							,							__lowerCamelCase   )
												self._len += 1
												return True
									elif stored.key == key:
												lowercase							=		_Item(__lowerCamelCase							,							__lowerCamelCase   )
												return True
									else:
												return False

						def        __a		(	self				:      Optional[Any]   )							->		bool:


									'''simple docstring'''

									lowercase							=		len(self._buckets   ) * self._capacity_factor
									return len(self   ) >= int(__lowerCamelCase   )

						def        __a		(	self				:      Tuple   )							->		bool:


									'''simple docstring'''

									if len(self._buckets   ) <= self._initial_block_size:
												return False
									lowercase							=		len(self._buckets   ) * self._capacity_factor / 2
									return len(self   ) < limit

						def        __a		(	self				:      Optional[Any]							,							__lowerCamelCase				:      int   )							->		None:


									'''simple docstring'''

									lowercase							=		self._buckets
									lowercase							=		[None] * new_size
									lowercase							=		0
									for item in old_buckets:
												if item:
															self._add_item(item.key							,							item.val   )

						def        __a		(	self				:      List[str]   )							->		None:


									'''simple docstring'''

									self._resize(len(self._buckets   ) * 2   )

						def        __a		(	self				:      Any   )							->		None:


									'''simple docstring'''

									self._resize(len(self._buckets   ) // 2   )

						def        __a		(	self				:      Optional[int]							,							__lowerCamelCase				:      KEY   )							->		Iterator[int]:


									'''simple docstring'''

									lowercase							=		self._get_bucket_index(__lowerCamelCase   )
									for _ in range(len(self._buckets   )   ):
												yield ind
												lowercase							=		self._get_next_ind(__lowerCamelCase   )

						def        __a		(	self				:      Optional[int]							,							__lowerCamelCase				:      KEY							,							__lowerCamelCase				:      VAL   )							->		None:


									'''simple docstring'''

									for ind in self._iterate_buckets(__lowerCamelCase   ):
												if self._try_set(__lowerCamelCase							,							__lowerCamelCase							,							__lowerCamelCase   ):
															break

						def __setitem__(	self				:      Optional[int]							,							__lowerCamelCase				:      KEY							,							__lowerCamelCase				:      VAL   )							->		None:


									'''simple docstring'''

									if self._is_full():
												self._size_up()

									self._add_item(__lowerCamelCase							,							__lowerCamelCase   )

						def __delitem__(	self				:      List[str]							,							__lowerCamelCase				:      KEY   )							->		None:


									'''simple docstring'''

									for ind in self._iterate_buckets(__lowerCamelCase   ):
												lowercase							=		self._buckets[ind]
												if item is None:
															raise KeyError(__lowerCamelCase   )
												if item is _deleted:
															continue
												if item.key == key:
															lowercase							=		_deleted
															self._len -= 1
															break
									if self._is_sparse():
												self._size_down()

						def __getitem__(	self				:      Any							,							__lowerCamelCase				:      KEY   )							->		VAL:


									'''simple docstring'''

									for ind in self._iterate_buckets(__lowerCamelCase   ):
												lowercase							=		self._buckets[ind]
												if item is None:
															break
												if item is _deleted:
															continue
												if item.key == key:
															return item.val
									raise KeyError(__lowerCamelCase   )

						def __len__(	self				:      str   )							->		int:


									'''simple docstring'''

									return self._len

						def __iter__(	self				:      Union[str, Any]   )							->		Iterator[KEY]:


									'''simple docstring'''

									yield from (item.key for item in self._buckets if item)



						def __repr__(	self				:      Any   )							->		str:


									'''simple docstring'''

									lowercase							=		''' ,'''.join(
									    f'{item.key}: {item.val}' for item in self._buckets if item   )
									return f'HashMap({val_string})'





