


'''simple docstring'''

def __UpperCamelCase   (			__lowerCamelCase		: int      ,  __lowerCamelCase		: bool = False				)      ->     bool:







					'''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 > 3_3170_4406_4679_8873_8596_1981 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
					_a						=		[
					    2047,
					    137_3653,
					    2532_6001,
					    32_1503_1751,
					    2_1523_0289_8747,
					    3_4747_4966_0383,
					    341_5500_7172_8321,
					    1,
					    382_5123_0565_4641_3051,
					    1,
					    1,
					    3186_6585_7834_0311_5116_7461,
					    3_3170_4406_4679_8873_8596_1981,
					]

					_a						=		[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
					for idx, _p in enumerate(__lowerCamelCase      ,  1				):
										if n < _p:
															# then we have our last prime to check
															_a						=		primes[:idx]
															break
					_a			,			_a						=		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:
										_a						=		False
										for r in range(__lowerCamelCase				):
															_a						=		pow(__lowerCamelCase      ,  d * 2**r      ,  __lowerCamelCase				)
															# see article for analysis explanation for m
															if (r == 0 and m == 1) or ((m + 1) % n == 0):
																				_a						=		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 __UpperCamelCase   (			)      ->     None:







					'''simple docstring'''






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

					assert not miller_rabin(83_8201				)
					assert miller_rabin(83_8207				)
					# 1_373_653

					assert not miller_rabin(1731_6001				)
					assert miller_rabin(1731_6017				)
					# 25_326_001

					assert not miller_rabin(30_7838_6641				)
					assert miller_rabin(30_7838_6653				)
					# 3_215_031_751

					assert not miller_rabin(1_7130_4557_4801				)
					assert miller_rabin(1_7130_4557_4819				)
					# 2_152_302_898_747

					assert not miller_rabin(2_7797_9972_8307				)
					assert miller_rabin(2_7797_9972_8327				)
					# 3_474_749_660_383

					assert not miller_rabin(113_8500_2390_9441				)
					assert miller_rabin(113_8500_2390_9527				)
					# 341_550_071_728_321

					assert not miller_rabin(127_5041_0188_4880_4351				)
					assert miller_rabin(127_5041_0188_4880_4391				)
					# 3_825_123_056_546_413_051

					assert not miller_rabin(796_6646_4458_5077_8779_1867				)
					assert miller_rabin(796_6646_4458_5077_8779_1951				)
					# 318_665_857_834_031_151_167_461

					assert not miller_rabin(5528_4067_7446_6478_9766_0333				)
					assert miller_rabin(5528_4067_7446_6478_9766_0359				)
					# 3_317_044_064_679_887_385_961_981
					# upper limit for probabilistic test


if __name__ == "__main__":
			test_miller_rabin()





'''simple docstring'''

from collections import defaultdict

from graphs.minimum_spanning_tree_prims import prisms_algorithm as mst






def __UpperCamelCase   (			)      ->     Tuple:







     '''simple docstring'''






     _a			,			_a						=		9, 14  # noqa: F841
     _a						=		[
         [0, 1, 4],
         [0, 7, 8],
         [1, 2, 8],
         [7, 8, 7],
         [7, 6, 1],
         [2, 8, 2],
         [8, 6, 6],
         [2, 3, 7],
         [2, 5, 4],
         [6, 5, 2],
         [3, 5, 14],
         [3, 4, 9],
         [5, 4, 10],
         [1, 7, 11],
     ]

     _a						=		defaultdict(__lowerCamelCase				)
     for nodea, nodea, cost in edges:
          adjancency[nodea].append([nodea, cost]				)
          adjancency[nodea].append([nodea, cost]				)

     _a						=		mst(__lowerCamelCase				)

     _a						=		[
         [7, 6, 1],
         [2, 8, 2],
         [6, 5, 2],
         [0, 1, 4],
         [2, 5, 4],
         [2, 3, 7],
         [0, 7, 8],
         [3, 4, 9],
     ]

     for answer in expected:
          _a						=		tuple(answer[:2]				)
          _a						=		tuple(edge[::-1]				)
          assert edge in result or reverse in result

