






"""simple docstring"""



class        __lowercase:






		def __init__(					self    ,						_SCREAMING_SNAKE_CASE)			->  None:




							"""simple docstring"""





							lowerCamelCase__				=data
							lowerCamelCase__				=42
							lowerCamelCase__				=42




def 						lowerCamelCase_				(  __A  :		Node			):
					lowerCamelCase__				=0
					lowerCamelCase__				=x




def 						lowerCamelCase_				(  __A  :		Node			,	__A  :		Node			):
					lowerCamelCase__				,     lowerCamelCase__				=find_set(__A			), find_set(__A			)
					if x == y:
										return

					elif x.rank > y.rank:
										lowerCamelCase__				=x
					else:
										lowerCamelCase__				=y
										if x.rank == y.rank:
															y.rank += 1




def 						lowerCamelCase_				(  __A  :		Node			):
					if x != x.parent:
										lowerCamelCase__				=find_set(x.parent			)
					return x.parent




def 						lowerCamelCase_				(  __A  :		Node			):
					lowerCamelCase__				=({0, 1, 2}, {3, 4, 5})
					for s in sets:
										if node.data in s:
															return s
					lowerCamelCase__				=f"{node.data} is not in {sets}"
					raise ValueError(__A			)




def 						lowerCamelCase_				(  ):
					lowerCamelCase__				=[Node(__A			) for i in range(6			)]
					for v in vertex:
										make_set(__A			)

					union_set(vertex[0]			,	vertex[1]			)
					union_set(vertex[1]			,	vertex[2]			)
					union_set(vertex[3]			,	vertex[4]			)
					union_set(vertex[3]			,	vertex[5]			)

					for nodea in vertex:
										for nodea in vertex:
															if find_python_set(__A			).isdisjoint(find_python_set(__A			)			):
																				assert find_set(__A			) != find_set(__A			)
															else:
																				assert find_set(__A			) == find_set(__A			)


if __name__ == "__main__":
						test_disjoint_set()







"""simple docstring"""



from __future__ import annotations




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			,	__A  :		int			):
					assert n > 1 and a > 0 and greatest_common_divisor(__A			,	__A			) == 1
					((lowerCamelCase__)				,     (lowerCamelCase__)				,     (lowerCamelCase__))				=extended_gcd(__A			,	__A			)  # Implemented below
					lowerCamelCase__				=(b * s) % n
					return x




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			):
					((lowerCamelCase__)				,     (lowerCamelCase__))				=extended_euclid(__A			,	__A			)  # Implemented below
					if b < 0:
										lowerCamelCase__				=(b % n + n) % n
					return b




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			,	__A  :		int			):
					lowerCamelCase__				=invert_modulo(__A			,	__A			)
					lowerCamelCase__				=(b * s) % n
					return x




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			):
					assert a >= 0 and b >= 0

					if b == 0:
										lowerCamelCase__				,     lowerCamelCase__				,     lowerCamelCase__				=a, 1, 0
					else:
										((lowerCamelCase__)				,     (lowerCamelCase__)				,     (lowerCamelCase__))				=extended_gcd(__A			,	a % b			)
										lowerCamelCase__				=q
										lowerCamelCase__				=p - q * (a // b)

					assert a % d == 0 and b % d == 0
					assert d == a * x + b * y

					return (d, x, y)




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			):
					if b == 0:
										return (1, 0)
					((lowerCamelCase__)				,     (lowerCamelCase__))				=extended_euclid(__A			,	a % b			)
					lowerCamelCase__				=a // b
					return (y, x - k * y)




def 						lowerCamelCase_				(  __A  :		int			,	__A  :		int			):
					if a < b:
										lowerCamelCase__				,     lowerCamelCase__				=b, a

					while a % b != 0:
										lowerCamelCase__				,     lowerCamelCase__				=b, a % b

					return b


if __name__ == "__main__":
						from doctest import testmod

						testmod(name="modular_division", verbose=True)
						testmod(name="modular_division2", verbose=True)
						testmod(name="invert_modulo", verbose=True)
						testmod(name="extended_gcd", verbose=True)
						testmod(name="extended_euclid", verbose=True)
						testmod(name="greatest_common_divisor", verbose=True)