code: 
  
  
  
  
  
  
  from __future__ import annotations
  
  from queue import Queue
  
  
  
  
  
  def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase					)   -> tuple[int, int]:
  
  					'''simple docstring'''
  					a ^= b
  					b ^= a
  					a ^= b
  					return a, b
  
  
  
  
  
  def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase					)   -> list[list[int]]:
  
  					'''simple docstring'''
  					UpperCAmelCase__			:     List[Any]										= 1
  					while (1 << j) < max_node:
  										for i in range(1   ,       max_node + 1					):
  															UpperCAmelCase__			:     Optional[Any]										= parent[j - 1][parent[j - 1][i]]
  										j += 1
  					return parent
  
  
  
  
  
  def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase					)   -> int:
  
  					'''simple docstring'''
  
  
  					if level[u] < level[v]:
  										UpperCAmelCase__			,		UpperCAmelCase__			:     Optional[int]										= 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__			:     Tuple										= 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__			:     Dict										= parent[i][u], parent[i][v]
      # returning longest common ancestor of u,v
  					return parent[0][u]
  
  
  
  
  
  def    _lowerCamelCase	(	__lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase = 1   ,       )   -> tuple[list[int], list[list[int]]]:
  
  					'''simple docstring'''
  					UpperCAmelCase__			:     Union[str, Any]										= 0
  					UpperCAmelCase__			:     List[str]										= Queue(maxsize=__lowerCamelCase					)
  					q.put(__lowerCamelCase					)
  					while q.qsize() != 0:
  										UpperCAmelCase__			:     Union[str, Any]										= q.get()
  										for v in graph[u]:
  															if level[v] == -1:
  																				UpperCAmelCase__			:     Optional[int]										= level[u] + 1
  																				q.put(__lowerCamelCase					)
  																				UpperCAmelCase__			:     int										= u
  					return level, parent
  
  
  
  
  
  def    _lowerCamelCase	(	)   -> None:
  
  					'''simple docstring'''
  					UpperCAmelCase__			:     List[Any]										= 13
  					# initializing with 0
  					UpperCAmelCase__			:     List[str]										= [[0 for _ in range(max_node + 10					)] for _ in range(20					)]
  					# initializing with -1 which means every node is unvisited
  					UpperCAmelCase__			:     Optional[Any]										= [-1 for _ in range(max_node + 10					)]
  					UpperCAmelCase__			:     Optional[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__			:     List[Any]										= breadth_first_search(__lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase   ,       __lowerCamelCase   ,       1					)
  					UpperCAmelCase__			:     Union[str, 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()
  
  
  
  
  
  
  
style_context: 
  
  
  
  
  
  
  from .stack import Stack
  
  
  
  
  
  def    _lowerCamelCase	(	__lowerCamelCase					)   -> bool:
  
       '''simple docstring'''
       UpperCAmelCase__			:     Stack[str]										= Stack()
       UpperCAmelCase__			:     str										= {"""(""": """)""", """[""": """]""", """{""": """}"""}
       for bracket in parentheses:
            if bracket in bracket_pairs:
                 stack.push(__lowerCamelCase					)
            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()
  
        SCREAMING_SNAKE_CASE__		:       Any   							=							["""((()))""", """((())""", """(()))"""]
        print("""Balanced parentheses demonstration:\n""")
        for example in examples:
              SCREAMING_SNAKE_CASE__		:       List[str]   							=							"""""" if balanced_parentheses(example) else """not """
              print(f'''{example} is {not_str}balanced''')
  
  
  
  
  
  
  