

from __future__ import annotations

from queue import Queue







def  UpperCAmelCase_   (_lowerCAmelCase :		Any     ,			_lowerCAmelCase :		Union[str, Any]		):
			a ^= b
			b ^= a
			a ^= b
			return a, b







def  UpperCAmelCase_   (_lowerCAmelCase :		Optional[Any]     ,			_lowerCAmelCase :		Optional[Any]		):
			__UpperCamelCase    :    str								=      1
			while (1 << j) < max_node:
						for i in range(1     ,			max_node + 1		):
									__UpperCamelCase    :    List[str]								=      parent[j - 1][parent[j - 1][i]]
						j += 1
			return parent







def  UpperCAmelCase_   (_lowerCAmelCase :		str     ,			_lowerCAmelCase :		Optional[int]     ,			_lowerCAmelCase :		str     ,			_lowerCAmelCase :		str		):
			# u must be deeper in the tree than v
			if level[u] < level[v]:
						__UpperCamelCase    :    Optional[Any]								=      swap(_lowerCAmelCase     ,			_lowerCAmelCase		)
			# making depth of u same as depth of v
			for i in range(18     ,			-1     ,			-1		):
						if level[u] - (1 << i) >= level[v]:
									__UpperCamelCase    :    str								=      parent[i][u]
    # at the same depth if u==v that mean lca is found
			if u == v:
						return u
			# moving both nodes upwards till lca in found
			for i in range(18     ,			-1     ,			-1		):
						if parent[i][u] not in [0, parent[i][v]]:
									__UpperCamelCase    :    int								=      parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
			return parent[0][u]







def  UpperCAmelCase_   (_lowerCAmelCase :		List[str]     ,			_lowerCAmelCase :		str     ,			_lowerCAmelCase :		Tuple     ,			_lowerCAmelCase :		int     ,			_lowerCAmelCase :		Tuple = 1     ,			):
			__UpperCamelCase    :    Any								=      0
			__UpperCamelCase    :    Queue[int]								=      Queue(maxsize=_lowerCAmelCase		)
			q.put(_lowerCAmelCase		)
			while q.qsize() != 0:
						__UpperCamelCase    :    Tuple								=      q.get()
						for v in graph[u]:
									if level[v] == -1:
												__UpperCamelCase    :    Tuple								=      level[u] + 1
												q.put(_lowerCAmelCase		)
												__UpperCamelCase    :    Union[str, Any]								=      u
			return level, parent







def  UpperCAmelCase_   ():
			__UpperCamelCase    :    List[str]								=      13
			# initializing with 0
			__UpperCamelCase    :    int								=      [[0 for _ in range(max_node + 10		)] for _ in range(20		)]
			# initializing with -1 which means every node is unvisited
			__UpperCamelCase    :    Optional[int]								=      [-1 for _ in range(max_node + 10		)]
			__UpperCamelCase    :    dict[int, list[int]]								=      {
			    1: [2, 3, 4],
			    2: [5],
			    3: [6, 7],
			    4: [8],
			    5: [9, 10],
			    6: [11],
			    7: [],
			    8: [12, 13],
			    9: [],
			    10: [],
			    11: [],
			    12: [],
			    13: [],
			}
			__UpperCamelCase    :    Optional[Any]								=      breadth_first_search(_lowerCAmelCase     ,			_lowerCAmelCase     ,			_lowerCAmelCase     ,			_lowerCAmelCase     ,			1		)
			__UpperCamelCase    :    List[Any]								=      create_sparse(_lowerCAmelCase     ,			_lowerCAmelCase		)
			print("LCA of node 1 and 3 is: "     ,			lowest_common_ancestor(1     ,			3     ,			_lowerCAmelCase     ,			_lowerCAmelCase		)		)
			print("LCA of node 5 and 6 is: "     ,			lowest_common_ancestor(5     ,			6     ,			_lowerCAmelCase     ,			_lowerCAmelCase		)		)
			print("LCA of node 7 and 11 is: "     ,			lowest_common_ancestor(7     ,			11     ,			_lowerCAmelCase     ,			_lowerCAmelCase		)		)
			print("LCA of node 6 and 7 is: "     ,			lowest_common_ancestor(6     ,			7     ,			_lowerCAmelCase     ,			_lowerCAmelCase		)		)
			print("LCA of node 4 and 12 is: "     ,			lowest_common_ancestor(4     ,			12     ,			_lowerCAmelCase     ,			_lowerCAmelCase		)		)
			print("LCA of node 8 and 8 is: "     ,			lowest_common_ancestor(8     ,			8     ,			_lowerCAmelCase     ,			_lowerCAmelCase		)		)


if __name__ == "__main__":
					main()


import random
import sys

from . import cryptomath_module as cryptomath

lowercase     :       Optional[Any]        =       (
    r" !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`"
    r"abcdefghijklmnopqrstuvwxyz{|}~"
)







def  UpperCAmelCase_   (_lowerCAmelCase :		int     ,			_lowerCAmelCase :		int     ,			_lowerCAmelCase :		str		):
			if mode == "encrypt":
						if key_a == 1:
									sys.exit(
									    "The affine cipher becomes weak when key "
									    "A is set to 1. Choose different key"		)
						if key_b == 0:
									sys.exit(
									    "The affine cipher becomes weak when key "
									    "B is set to 0. Choose different key"		)
			if key_a < 0 or key_b < 0 or key_b > len(_lowerCAmelCase		) - 1:
						sys.exit(
						    "Key A must be greater than 0 and key B must "
						    F'''be between 0 and {len(_lowerCAmelCase		) - 1}.'''		)
			if cryptomath.gcd(_lowerCAmelCase     ,			len(_lowerCAmelCase		)		) != 1:
						sys.exit(
						    F'''Key A {key_a} and the symbol set size {len(_lowerCAmelCase		)} '''
						    "are not relatively prime. Choose a different key."		)







def  UpperCAmelCase_   (_lowerCAmelCase :		int     ,			_lowerCAmelCase :		str		):
			__UpperCamelCase							,				__UpperCamelCase    :    int								=      divmod(_lowerCAmelCase     ,			len(_lowerCAmelCase		)		)
			check_keys(_lowerCAmelCase     ,			_lowerCAmelCase     ,			"encrypt"		)
			__UpperCamelCase    :    List[Any]								=      ""
			for symbol in message:
						if symbol in SYMBOLS:
									__UpperCamelCase    :    Tuple								=      SYMBOLS.find(_lowerCAmelCase		)
									cipher_text += SYMBOLS[(sym_index * key_a + key_b) % len(_lowerCAmelCase		)]
						else:
									cipher_text += symbol
			return cipher_text







def  UpperCAmelCase_   (_lowerCAmelCase :		int     ,			_lowerCAmelCase :		str		):
			__UpperCamelCase							,				__UpperCamelCase    :    List[str]								=      divmod(_lowerCAmelCase     ,			len(_lowerCAmelCase		)		)
			check_keys(_lowerCAmelCase     ,			_lowerCAmelCase     ,			"decrypt"		)
			__UpperCamelCase    :    List[Any]								=      ""
			__UpperCamelCase    :    Tuple								=      cryptomath.find_mod_inverse(_lowerCAmelCase     ,			len(_lowerCAmelCase		)		)
			for symbol in message:
						if symbol in SYMBOLS:
									__UpperCamelCase    :    List[Any]								=      SYMBOLS.find(_lowerCAmelCase		)
									plain_text += SYMBOLS[
									    (sym_index - key_b) * mod_inverse_of_key_a % len(_lowerCAmelCase		)
									]
						else:
									plain_text += symbol
			return plain_text







def  UpperCAmelCase_   ():
			while True:
						__UpperCamelCase    :    Optional[int]								=      random.randint(2     ,			len(_lowerCAmelCase		)		)
						__UpperCamelCase    :    Optional[int]								=      random.randint(2     ,			len(_lowerCAmelCase		)		)
						if cryptomath.gcd(_lowerCAmelCase     ,			len(_lowerCAmelCase		)		) == 1 and key_b % len(_lowerCAmelCase		) != 0:
									return key_b * len(_lowerCAmelCase		) + key_b







def  UpperCAmelCase_   ():
			__UpperCamelCase    :    List[Any]								=      input("Enter message: "		).strip()
			__UpperCamelCase    :    List[Any]								=      int(input("Enter key [2000 - 9000]: "		).strip()		)
			__UpperCamelCase    :    Optional[int]								=      input("Encrypt/Decrypt [E/D]: "		).strip().lower()

			if mode.startswith("e"		):
						__UpperCamelCase    :    str								=      "encrypt"
						__UpperCamelCase    :    str								=      encrypt_message(_lowerCAmelCase     ,			_lowerCAmelCase		)
			elif mode.startswith("d"		):
						__UpperCamelCase    :    int								=      "decrypt"
						__UpperCamelCase    :    Dict								=      decrypt_message(_lowerCAmelCase     ,			_lowerCAmelCase		)
			print(F'''\n{mode.title()}ed text: \n{translated}'''		)


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					# main()