code: 
  
  
  
  '''simple docstring'''
  
  
  
  from __future__ import annotations
  
  from queue import Queue
  
  
  
  
  
  
  
  def _lowercase   (  __A							,__A       ):
  
  
  
   '''simple docstring'''
  
  
  
   a ^= b
   b ^= a
   a ^= b
   return a, b
  
  
  
  
  
  
  
  def _lowercase   (  __A							,__A       ):
  
  
  
   '''simple docstring'''
  
  
  
   __UpperCamelCase				      =  1
   while (1 << j) < max_node:
    for i in range(1							,max_node + 1       ):
     __UpperCamelCase				      =  parent[j - 1][parent[j - 1][i]]
    j += 1
   return parent
  
  
  
  
  
  
  
  def _lowercase   (  __A							,__A							,__A							,__A       ):
  
  
  
   '''simple docstring'''
  
  
  
   if level[u] < level[v]:
    __UpperCamelCase      ,		__UpperCamelCase				      =  swap(__A							,__A       )
   # making depth of u same as depth of v
   for i in range(18							,-1							,-1       ):
    if level[u] - (1 << i) >= level[v]:
     __UpperCamelCase				      =  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				      =  parent[i][u], parent[i][v]
      # returning longest common ancestor of u,v
   return parent[0][u]
  
  
  
  
  
  
  
  def _lowercase   (  __A							,__A							,__A							,__A							,__A = 1							,):
  
  
  
   '''simple docstring'''
  
  
  
   __UpperCamelCase				      =  0
   __UpperCamelCase				      =  Queue(maxsize=__A       )
   q.put(__A       )
   while q.qsize() != 0:
    __UpperCamelCase				      =  q.get()
    for v in graph[u]:
     if level[v] == -1:
      __UpperCamelCase				      =  level[u] + 1
      q.put(__A       )
      __UpperCamelCase				      =  u
   return level, parent
  
  
  
  
  
  
  
  def _lowercase   (  ):
  
  
  
   '''simple docstring'''
  
  
  
   __UpperCamelCase				      =  13
   # initializing with 0
   __UpperCamelCase				      =  [[0 for _ in range(max_node + 10       )] for _ in range(20       )]
   # initializing with -1 which means every node is unvisited
   __UpperCamelCase				      =  [-1 for _ in range(max_node + 10       )]
   __UpperCamelCase				      =  {
       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				      =  breadth_first_search(__A							,__A							,__A							,__A							,1       )
   __UpperCamelCase				      =  create_sparse(__A							,__A       )
   print("""LCA of node 1 and 3 is: """							,lowest_common_ancestor(1							,3							,__A							,__A       )       )
   print("""LCA of node 5 and 6 is: """							,lowest_common_ancestor(5							,6							,__A							,__A       )       )
   print("""LCA of node 7 and 11 is: """							,lowest_common_ancestor(7							,11							,__A							,__A       )       )
   print("""LCA of node 6 and 7 is: """							,lowest_common_ancestor(6							,7							,__A							,__A       )       )
   print("""LCA of node 4 and 12 is: """							,lowest_common_ancestor(4							,12							,__A							,__A       )       )
   print("""LCA of node 8 and 8 is: """							,lowest_common_ancestor(8							,8							,__A							,__A       )       )
  
  
  if __name__ == "__main__":
   main()
  
  
  
  
  
  
style_context: 
  
  
  
  '''simple docstring'''
  
  
  
  from .stack import Stack
  
  
  
  
  
  
  
  def _lowercase   (  __A       ):
  
  
  
   '''simple docstring'''
  
  
  
   __UpperCamelCase				      =  Stack()
   __UpperCamelCase				      =  {"""(""": """)""", """[""": """]""", """{""": """}"""}
   for bracket in parentheses:
    if bracket in bracket_pairs:
     stack.push(__A       )
    elif bracket in (")", "]", "}"):
     if stack.is_empty() or bracket_pairs[stack.pop()] != bracket:
      return False
   return stack.is_empty()
  
  
  if __name__ == "__main__":
   from doctest import testmod
  
   testmod()
  
   a__						:			List[Any]										=			['((()))', '((())', '(()))']
   print('Balanced parentheses demonstration:\n')
   for example in examples:
    a__						:			int										=			'' if balanced_parentheses(example) else 'not '
    print(f'''{example} is {not_str}balanced''')
  
  
  
  
  
  