






from __future__ import annotations

from queue import Queue



def 				_lowerCAmelCase      (_lowerCAmelCase				,		_lowerCAmelCase):
					a ^= b
					b ^= a
					a ^= b
					return a, b



def 				_lowerCAmelCase      (_lowerCAmelCase				,		_lowerCAmelCase):
					UpperCamelCase_											=				1
					while (1 << j) < max_node:
										for i in range(1				,		max_node + 1):
															UpperCamelCase_											=				parent[j - 1][parent[j - 1][i]]
										j += 1
					return parent



def 				_lowerCAmelCase      (_lowerCAmelCase				,		_lowerCAmelCase				,		_lowerCAmelCase				,		_lowerCAmelCase):
					# u must be deeper in the tree than v
					if level[u] < level[v]:
										UpperCamelCase_											=				swap(lowercase__				,		lowercase__)
					# making depth of u same as depth of v
					for i in range(18				,		-1				,		-1):
										if level[u] - (1 << i) >= level[v]:
															UpperCamelCase_											=				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_											=				parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
					return parent[0][u]



def 				_lowerCAmelCase      (_lowerCAmelCase				,		_lowerCAmelCase				,		_lowerCAmelCase				,		_lowerCAmelCase				,		_lowerCAmelCase = 1				,		):
					UpperCamelCase_											=				0
					UpperCamelCase_											=				Queue(maxsize=lowercase__)
					q.put(lowercase__)
					while q.qsize() != 0:
										UpperCamelCase_											=				q.get()
										for v in graph[u]:
															if level[v] == -1:
																				UpperCamelCase_											=				level[u] + 1
																				q.put(lowercase__)
																				UpperCamelCase_											=				u
					return level, parent



def 				_lowerCAmelCase      ():
					UpperCamelCase_											=				13
					# initializing with 0
					UpperCamelCase_											=				[[0 for _ in range(max_node + 10)] for _ in range(20)]
					# initializing with -1 which means every node is unvisited
					UpperCamelCase_											=				[-1 for _ in range(max_node + 10)]
					UpperCamelCase_											=				{
					    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_											=				breadth_first_search(lowercase__				,		lowercase__				,		lowercase__				,		lowercase__				,		1)
					UpperCamelCase_											=				create_sparse(lowercase__				,		lowercase__)
					print("LCA of node 1 and 3 is: "				,		lowest_common_ancestor(1				,		3				,		lowercase__				,		lowercase__))
					print("LCA of node 5 and 6 is: "				,		lowest_common_ancestor(5				,		6				,		lowercase__				,		lowercase__))
					print("LCA of node 7 and 11 is: "				,		lowest_common_ancestor(7				,		11				,		lowercase__				,		lowercase__))
					print("LCA of node 6 and 7 is: "				,		lowest_common_ancestor(6				,		7				,		lowercase__				,		lowercase__))
					print("LCA of node 4 and 12 is: "				,		lowest_common_ancestor(4				,		12				,		lowercase__				,		lowercase__))
					print("LCA of node 8 and 8 is: "				,		lowest_common_ancestor(8				,		8				,		lowercase__				,		lowercase__))


if __name__ == "__main__":
	main()





from typing import Literal

UpperCAmelCase				:							Tuple								="""ABCDEFGHIJKLMNOPQRSTUVWXYZ"""



def 				_lowerCAmelCase      (_lowerCAmelCase				,		_lowerCAmelCase				,		_lowerCAmelCase):
					UpperCamelCase_											=				LETTERS if mode == "decrypt" else key
					UpperCamelCase_											=				key if mode == "decrypt" else LETTERS
					UpperCamelCase_											=				""
					# loop through each symbol in the message
					for symbol in message:
										if symbol.upper() in chars_a:
															# encrypt/decrypt the symbol
															UpperCamelCase_											=				chars_a.find(symbol.upper())
															if symbol.isupper():
																				translated += chars_b[sym_index].upper()
															else:
																				translated += chars_b[sym_index].lower()
										else:
															# symbol is not in LETTERS, just add it
															translated += symbol
					return translated



def 				_lowerCAmelCase      (_lowerCAmelCase				,		_lowerCAmelCase):
					return translate_message(_lowerCAmelCase				,		_lowerCAmelCase				,		"encrypt")



def 				_lowerCAmelCase      (_lowerCAmelCase				,		_lowerCAmelCase):
					return translate_message(_lowerCAmelCase				,		_lowerCAmelCase				,		"decrypt")



def 				_lowerCAmelCase      ():
					UpperCamelCase_											=				"Hello World"
					UpperCamelCase_											=				"QWERTYUIOPASDFGHJKLZXCVBNM"
					UpperCamelCase_											=				"decrypt"  # set to 'encrypt' or 'decrypt'

					if mode == "encrypt":
										UpperCamelCase_											=				encrypt_message(_lowerCAmelCase				,		_lowerCAmelCase)
					elif mode == "decrypt":
										UpperCamelCase_											=				decrypt_message(_lowerCAmelCase				,		_lowerCAmelCase)
					print(f"""Using the key {key}, the {mode}ed message is: {translated}""")


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	main()
