from __future__ import annotations

from queue import Queue






def  UpperCAmelCase__(    lowerCamelCase_				,						lowerCamelCase_	):



			"""simple docstring"""





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






def  UpperCAmelCase__(    lowerCamelCase_				,						lowerCamelCase_	):



			"""simple docstring"""





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






def  UpperCAmelCase__(    lowerCamelCase_				,						lowerCamelCase_				,						lowerCamelCase_				,						lowerCamelCase_	):



			"""simple docstring"""





			if level[u] < level[v]:
						_snake_case							,			_snake_case														=   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]:
									_snake_case														=   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]]:
									_snake_case							,			_snake_case														=   parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
			return parent[0][u]






def  UpperCAmelCase__(    lowerCamelCase_				,						lowerCamelCase_				,						lowerCamelCase_				,						lowerCamelCase_				,						lowerCamelCase_ = 1				,						):



			"""simple docstring"""





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






def  UpperCAmelCase__(    ):



			"""simple docstring"""





			_snake_case														=   13
			# initializing with 0
			_snake_case														=   [[0 for _ in range(max_node + 10	)] for _ in range(20	)]
			# initializing with -1 which means every node is unvisited
			_snake_case														=   [-1 for _ in range(max_node + 10	)]
			_snake_case														=   {
			    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: [],
			}
			_snake_case							,			_snake_case														=   breadth_first_search(lowerCamelCase_				,						lowerCamelCase_				,						lowerCamelCase_				,						lowerCamelCase_				,						1	)
			_snake_case														=   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()


def  UpperCAmelCase__(    lowerCamelCase_ = 1000	):



			"""simple docstring"""





			return sum(i for i in range(lowerCamelCase_	) if i % 3 == 0 or i % 5 == 0	)


if __name__ == "__main__":
			print(F"{solution() = }")

