from __future__ import annotations

from queue import Queue





def      __lowercase  (		lowerCamelCase      :  int						,						lowerCamelCase      :  int			):
 a ^= b
 b ^= a
 a ^= b
 return a, b





def      __lowercase  (		lowerCamelCase      :  int						,						lowerCamelCase      :  list[list[int]]			):
 UpperCamelCase_      :		Any				=      1
 while (1 << j) < max_node:
  for i in range(1						,						max_node + 1			):
   UpperCamelCase_      :		Union[str, Any]				=      parent[j - 1][parent[j - 1][i]]
  j += 1
 return parent





def      __lowercase  (		lowerCamelCase      :  int						,						lowerCamelCase      :  int						,						lowerCamelCase      :  list[int]						,						lowerCamelCase      :  list[list[int]]			):
 # u must be deeper in the tree than v
 if level[u] < level[v]:
  UpperCamelCase_,				UpperCamelCase_      :		str				=      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_      :		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_      :		List[Any]				=      parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
 return parent[0][u]





def      __lowercase  (		lowerCamelCase      :  list[int]						,						lowerCamelCase      :  list[list[int]]						,						lowerCamelCase      :  int						,						lowerCamelCase      :  dict[int, list[int]]						,						lowerCamelCase      :  int = 1						,						):
 UpperCamelCase_      :		Optional[int]				=      0
 UpperCamelCase_      :		Queue[int]				=      Queue(maxsize=lowerCamelCase			)
 q.put(lowerCamelCase			)
 while q.qsize() != 0:
  UpperCamelCase_      :		Tuple				=      q.get()
  for v in graph[u]:
   if level[v] == -1:
    UpperCamelCase_      :		Tuple				=      level[u] + 1
    q.put(lowerCamelCase			)
    UpperCamelCase_      :		Dict				=      u
 return level, parent





def      __lowercase  (		):
 UpperCamelCase_      :		Optional[int]				=      13
 # initializing with 0
 UpperCamelCase_      :		str				=      [[0 for _ in range(max_node + 10			)] for _ in range(20			)]
 # initializing with -1 which means every node is unvisited
 UpperCamelCase_      :		str				=      [-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_      :		Any				=      breadth_first_search(lowerCamelCase						,						lowerCamelCase						,						lowerCamelCase						,						lowerCamelCase						,						1			)
 UpperCamelCase_      :		Optional[int]				=      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()




from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

a_					      = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}





def      __lowercase  (		lowerCamelCase      :  dict						,						lowerCamelCase      :  str			):
 UpperCamelCase_      :		Tuple				=      {start}
 UpperCamelCase_      :		Optional[Any]				=      [start]
 UpperCamelCase_      :		Queue				=      Queue()
 queue.put(lowerCamelCase			)
 while not queue.empty():
  UpperCamelCase_      :		Union[str, Any]				=      queue.get()
  for w in graph[v]:
   if w not in explored:
    explored.add(lowerCamelCase			)
    result.append(lowerCamelCase			)
    queue.put(lowerCamelCase			)
 return result





def      __lowercase  (		lowerCamelCase      :  dict						,						lowerCamelCase      :  str			):
 UpperCamelCase_      :		Dict				=      {start}
 UpperCamelCase_      :		Optional[int]				=      [start]
 UpperCamelCase_      :		Union[str, Any]				=      deque([start]			)
 while queue:
  UpperCamelCase_      :		Optional[int]				=      queue.popleft()
  for child in graph[v]:
   if child not in visited:
    visited.add(lowerCamelCase			)
    result.append(lowerCamelCase			)
    queue.append(lowerCamelCase			)
 return result





def      __lowercase  (		lowerCamelCase      :  str			):
 UpperCamelCase_      :		str				=      F"from __main__ import G, {name}"
 UpperCamelCase_      :		int				=      10000
 UpperCamelCase_      :		Optional[Any]				=      timeit(F"{name}(G, 'A')"						,						setup=lowerCamelCase						,						number=lowerCamelCase			)
 print(F"{name:<35} finished {number} runs in {res:.5f} seconds"			)


if __name__ == "__main__":
   import doctest

   doctest.testmod()

   benchmark_function('breadth_first_search')
   benchmark_function('breadth_first_search_with_deque')
   # breadth_first_search                finished 10000 runs in 0.20999 seconds
   # breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds



