
class   UpperCamelCase_      :







						'''simple docstring'''



						def __init__(			self							:List[Any]     )  ->Optional[Any]:
										lowercase         =      0
										lowercase         =      0
										lowercase         =      {}





						def        SCREAMING_SNAKE_CASE(			self							:Optional[int]		,    lowerCAmelCase__							:List[Any]     )  ->Union[str, Any]:
										if vertex not in self.adjacency:
														lowercase         =      {}
														self.num_vertices += 1





						def        SCREAMING_SNAKE_CASE(			self							:Dict		,    lowerCAmelCase__							:Any		,    lowerCAmelCase__							:Union[str, Any]		,    lowerCAmelCase__							:int     )  ->int:
										self.add_vertex(lowerCAmelCase__     )
										self.add_vertex(lowerCAmelCase__     )

										if head == tail:
														return

										lowercase         =      weight
										lowercase         =      weight





						def        SCREAMING_SNAKE_CASE(			self							:Optional[int]     )  ->List[str]:
										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							:Union[str, Any]     )  ->Optional[Any]:
										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        SCREAMING_SNAKE_CASE(			self							:Optional[Any]     )  ->List[str]:
										lowercase         =      []
										for tail in self.adjacency:
														for head in self.adjacency[tail]:
																		output.append((tail, head, self.adjacency[head][tail])     )
										return output





						def        SCREAMING_SNAKE_CASE(			self							:Optional[int]     )  ->List[Any]:
										return self.adjacency.keys()





						@staticmethod
						def        SCREAMING_SNAKE_CASE(			lowerCAmelCase__							:Optional[int]=None		,    lowerCAmelCase__							:List[str]=None     )  ->Optional[int]:
										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   UpperCamelCase_      :







												'''simple docstring'''



												def __init__(			self							:Dict     )  ->Any:
																lowercase         =      {}
																lowercase         =      {}





												def __len__(			self							:Any     )  ->List[Any]:
																return len(self.parent     )





												def        SCREAMING_SNAKE_CASE(			self							:Union[str, Any]		,    lowerCAmelCase__							:Optional[Any]     )  ->Dict:
																if item in self.parent:
																				return self.find(lowerCAmelCase__     )

																lowercase         =      item
																lowercase         =      0
																return item





												def        SCREAMING_SNAKE_CASE(			self							:Optional[int]		,    lowerCAmelCase__							:int     )  ->int:
																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        SCREAMING_SNAKE_CASE(			self							:Dict		,    lowerCAmelCase__							:List[Any]		,    lowerCAmelCase__							:Optional[Any]     )  ->Optional[Any]:
																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        SCREAMING_SNAKE_CASE(			lowerCAmelCase__							:List[str]     )  ->List[str]:
										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


def  __snake_case							(	__magic_name__		,    __magic_name__ = False						):







				'''simple docstring'''


				if n == 2:
								return True
				if not n % 2 or n < 2:
								return False
				if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
								return False
				if n > 3317044064679887385961981 and not allow_probable:
								raise ValueError(
								    "Warning: upper bound of deterministic test is exceeded. "
								    "Pass allow_probable=True to allow probabilistic test. "
								    "A return value of True indicates a probable prime."						)
				# array bounds provided by analysis
				lowercase         =      [
				    2047,
				    1373653,
				    25326001,
				    3215031751,
				    2152302898747,
				    3474749660383,
				    341550071728321,
				    1,
				    3825123056546413051,
				    1,
				    1,
				    318665857834031151167461,
				    3317044064679887385961981,
				]

				lowercase         =      [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
				for idx, _p in enumerate(__magic_name__		,    1						):
								if n < _p:
												# then we have our last prime to check
												lowercase         =      primes[:idx]
												break
				lowercase     ,	lowercase         =      n - 1, 0
				# break up n -1 into a power of 2 (s) and
				# remaining odd component
				# essentially, solve for d * 2 ** s == n - 1
				while d % 2 == 0:
								d //= 2
								s += 1
				for prime in plist:
								lowercase         =      False
								for r in range(__magic_name__						):
												lowercase         =      pow(__magic_name__		,    d * 2**r		,    __magic_name__						)
												# see article for analysis explanation for m
												if (r == 0 and m == 1) or ((m + 1) % n == 0):
																lowercase         =      True
																# this loop will not determine compositeness
																break
								if pr:
												continue
								# if pr is False, then the above loop never evaluated to true,
								# and the n MUST be composite
								return False
				return True

def  __snake_case							(	):







				'''simple docstring'''


				assert not miller_rabin(561						)
				assert miller_rabin(563						)
				# 2047

				assert not miller_rabin(838201						)
				assert miller_rabin(838207						)
				# 1_373_653

				assert not miller_rabin(17316001						)
				assert miller_rabin(17316017						)
				# 25_326_001

				assert not miller_rabin(3078386641						)
				assert miller_rabin(3078386653						)
				# 3_215_031_751

				assert not miller_rabin(1713045574801						)
				assert miller_rabin(1713045574819						)
				# 2_152_302_898_747

				assert not miller_rabin(2779799728307						)
				assert miller_rabin(2779799728327						)
				# 3_474_749_660_383

				assert not miller_rabin(113850023909441						)
				assert miller_rabin(113850023909527						)
				# 341_550_071_728_321

				assert not miller_rabin(1275041018848804351						)
				assert miller_rabin(1275041018848804391						)
				# 3_825_123_056_546_413_051

				assert not miller_rabin(79666464458507787791867						)
				assert miller_rabin(79666464458507787791951						)
				# 318_665_857_834_031_151_167_461

				assert not miller_rabin(552840677446647897660333						)
				assert miller_rabin(552840677446647897660359						)
				# 3_317_044_064_679_887_385_961_981
				# upper limit for probabilistic test


if __name__ == "__main__":
						test_miller_rabin()
