




"""simple docstring"""

from __future__ import annotations

from queue import Queue



def 				a (						__snake_case     :				int,    __snake_case     :				int  ):



				'''simple docstring'''





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



def 				a (						__snake_case     :				int,    __snake_case     :				list[list[int]]  ):



				'''simple docstring'''





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



def 				a (						__snake_case     :				int,    __snake_case     :				int,    __snake_case     :				list[int],    __snake_case     :				list[list[int]]  ):



				'''simple docstring'''





				if level[u] < level[v]:
								UpperCAmelCase_			,UpperCAmelCase_					:List[str]      			=      swap(__snake_case,    __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]:
												UpperCAmelCase_					:Union[str, 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]]:
												UpperCAmelCase_			,UpperCAmelCase_					:str      			=      parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
				return parent[0][u]



def 				a (						__snake_case     :				list[int],    __snake_case     :				list[list[int]],    __snake_case     :				int,    __snake_case     :				dict[int, list[int]],    __snake_case     :				int = 1,    ):



				'''simple docstring'''





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



def 				a (						):



				'''simple docstring'''





				UpperCAmelCase_					:List[str]      			=      13
				# initializing with 0
				UpperCAmelCase_					:Optional[Any]      			=      [[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_			,UpperCAmelCase_					:Optional[int]      			=      breadth_first_search(__snake_case,    __snake_case,    __snake_case,    __snake_case,    1  )
				UpperCAmelCase_					:Union[str, Any]      			=      create_sparse(__snake_case,    __snake_case  )
				print('''LCA of node 1 and 3 is: ''',    lowest_common_ancestor(1,    3,    __snake_case,    __snake_case  )  )
				print('''LCA of node 5 and 6 is: ''',    lowest_common_ancestor(5,    6,    __snake_case,    __snake_case  )  )
				print('''LCA of node 7 and 11 is: ''',    lowest_common_ancestor(7,    11,    __snake_case,    __snake_case  )  )
				print('''LCA of node 6 and 7 is: ''',    lowest_common_ancestor(6,    7,    __snake_case,    __snake_case  )  )
				print('''LCA of node 4 and 12 is: ''',    lowest_common_ancestor(4,    12,    __snake_case,    __snake_case  )  )
				print('''LCA of node 8 and 8 is: ''',    lowest_common_ancestor(8,    8,    __snake_case,    __snake_case  )  )


if __name__ == "__main__":
						main()








"""simple docstring"""

def 				a (						__snake_case     :				int  ):



				'''simple docstring'''





				if not isinstance(__snake_case,    __snake_case  ) or number < 0:
								raise ValueError('''Input must be a non-negative integer'''  )

				UpperCAmelCase_					:Optional[Any]      			=      number & ~(number - 1)
				UpperCAmelCase_					:List[str]      			=      0
				while intermediate:
								intermediate >>= 1
								index += 1
				return index - 1


if __name__ == "__main__":
						import doctest

						doctest.testmod(verbose=True)


