


'''simple docstring'''


from __future__ import annotations

from queue import Queue







def       snake_case_       (  SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					):







				"""simple docstring"""





				a ^= b
				b ^= a
				a ^= b
				return a, b







def       snake_case_       (  SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE			:	int							=				1
				while (1 << j) < max_node:
								for i in range(1							,				max_node + 1					):
												_SCREAMING_SNAKE_CASE			:	Optional[int]							=				parent[j - 1][parent[j - 1][i]]
								j += 1
				return parent







def       snake_case_       (  SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					):







				"""simple docstring"""





				if level[u] < level[v]:
								_SCREAMING_SNAKE_CASE		,	_SCREAMING_SNAKE_CASE			:	Dict							=				swap(SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)
				# making depth of u same as depth of v
				for i in range(18							,				-1							,				-1					):
								if level[u] - (1 << i) >= level[v]:
												_SCREAMING_SNAKE_CASE			:	List[Any]							=				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]]:
												_SCREAMING_SNAKE_CASE		,	_SCREAMING_SNAKE_CASE			:	str							=				parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
				return parent[0][u]







def       snake_case_       (  SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__ = 1							,				):







				"""simple docstring"""





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







def       snake_case_       (  ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE			:	Any							=				13
				# initializing with 0
				_SCREAMING_SNAKE_CASE			:	Optional[Any]							=				[[0 for _ in range(max_node + 10					)] for _ in range(20					)]
				# initializing with -1 which means every node is unvisited
				_SCREAMING_SNAKE_CASE			:	List[str]							=				[-1 for _ in range(max_node + 10					)]
				_SCREAMING_SNAKE_CASE			:	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: [],
				}
				_SCREAMING_SNAKE_CASE		,	_SCREAMING_SNAKE_CASE			:	List[str]							=				breadth_first_search(SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				1					)
				_SCREAMING_SNAKE_CASE			:	Optional[int]							=				create_sparse(SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)
				print("""LCA of node 1 and 3 is: """							,				lowest_common_ancestor(1							,				3							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)					)
				print("""LCA of node 5 and 6 is: """							,				lowest_common_ancestor(5							,				6							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)					)
				print("""LCA of node 7 and 11 is: """							,				lowest_common_ancestor(7							,				11							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)					)
				print("""LCA of node 6 and 7 is: """							,				lowest_common_ancestor(6							,				7							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)					)
				print("""LCA of node 4 and 12 is: """							,				lowest_common_ancestor(4							,				12							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)					)
				print("""LCA of node 8 and 8 is: """							,				lowest_common_ancestor(8							,				8							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					)					)


if __name__ == "__main__":
				main()








'''simple docstring'''


def       snake_case_       (  SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE			:	Tuple							=				1
				while b > 0:
								if b & 1:
												res *= a

								a *= a
								b >>= 1

				return res







def       snake_case_       (  SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__							,				SCREAMING_SNAKE_CASE__					):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE			:	Union[str, Any]							=				1
				while b > 0:
								if b & 1:
												_SCREAMING_SNAKE_CASE			:	Tuple							=				((res % c) * (a % c)) % c

								a *= a
								b >>= 1

				return res




