
from __future__ import annotations

from queue import Queue
def     UpperCAmelCase__							(       __magic_name__						:     int							,  __magic_name__						:     int  ):


     '''simple docstring'''

     a ^= b
     b ^= a
     a ^= b
     return a, b
def     UpperCAmelCase__							(       __magic_name__						:     int							,  __magic_name__						:     list[list[int]]  ):


     '''simple docstring'''

     lowerCAmelCase		:					Optional[Any]  	=     1
     while (1 << j) < max_node:
          for i in range(1							,  max_node + 1  ):
               lowerCAmelCase		:					str  	=     parent[j - 1][parent[j - 1][i]]
          j += 1
     return parent
def     UpperCAmelCase__							(       __magic_name__						:     int							,  __magic_name__						:     int							,  __magic_name__						:     list[int]							,  __magic_name__						:     list[list[int]]  ):


     '''simple docstring'''

     if level[u] < level[v]:
          lowerCAmelCase		:					Union[str, Any]  	=     swap(__magic_name__							,  __magic_name__  )
     # making depth of u same as depth of v
     for i in range(18							,  -1							,  -1  ):
          if level[u] - (1 << i) >= level[v]:
               lowerCAmelCase		:					Optional[int]  	=     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]]:
               lowerCAmelCase		:					str  	=     parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
     return parent[0][u]
def     UpperCAmelCase__							(       __magic_name__						:     list[int]							,  __magic_name__						:     list[list[int]]							,  __magic_name__						:     int							,  __magic_name__						:     dict[int, list[int]]							,  __magic_name__						:     int = 1							,  ):


     '''simple docstring'''

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


     '''simple docstring'''

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


if __name__ == "__main__":
  main()


from ..utils import requires_backends


__SCREAMING_SNAKE_CASE			:   Union[str, Any]         =     None


class 		__magic_name__   :





		def __init__(							self    :	Optional[int]						,  *lowerCamelCase__    :	List[str]						,  **lowerCamelCase__    :	Optional[Any]				):
							requires_backends(self						,  ['''detectron2''']				)





		@classmethod
		def       _A							(							cls    :	Dict						,  *lowerCamelCase__    :	List[str]						,  **lowerCamelCase__    :	Optional[Any]				):
							requires_backends(cls						,  ['''detectron2''']				)
