

"""simple docstring"""




from __future__ import annotations

from queue import Queue
def      lowerCAmelCase  (    __UpperCamelCase							,			__UpperCamelCase					):
 '''simple docstring'''





 a ^= b
 b ^= a
 a ^= b
 return a, b
def      lowerCAmelCase  (    __UpperCamelCase							,			__UpperCamelCase					):
 '''simple docstring'''





 UpperCAmelCase__    :     Optional[Any]          =    1
 while (1 << j) < max_node:
  for i in range(1							,			max_node + 1					):
   UpperCAmelCase__    :     Tuple          =    parent[j - 1][parent[j - 1][i]]
  j += 1
 return parent
def      lowerCAmelCase  (    __UpperCamelCase							,			__UpperCamelCase							,			__UpperCamelCase							,			__UpperCamelCase					):
 '''simple docstring'''





 if level[u] < level[v]:
  UpperCAmelCase__    :     Optional[Any]          =    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]:
   UpperCAmelCase__    :     Optional[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__    :     List[str]          =    parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
 return parent[0][u]
def      lowerCAmelCase  (    __UpperCamelCase							,			__UpperCamelCase							,			__UpperCamelCase							,			__UpperCamelCase							,			__UpperCamelCase = 1							,			):
 '''simple docstring'''





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





 UpperCAmelCase__    :     Optional[Any]          =    13
 # initializing with 0
 UpperCAmelCase__    :     Any          =    [[0 for _ in range(max_node + 10					)] for _ in range(20					)]
 # initializing with -1 which means every node is unvisited
 UpperCAmelCase__    :     Any          =    [-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__    :     Tuple          =    breadth_first_search(lowerCAmelCase_							,			lowerCAmelCase_							,			lowerCAmelCase_							,			lowerCAmelCase_							,			1					)
 UpperCAmelCase__    :     Any          =    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()







'''simple docstring'''

from itertools import permutations







def __A  (    ):
     _UpperCAmelCase					:  Union[str, Any]         =    list(map("""""".join ,       permutations("""0123456789"""       )       )       )
     return result[99_9999]


if __name__ == "__main__":
   print(solution())


