code: 
  
  
  
  
  
  
  from __future__ import annotations
  
  from queue import Queue
  
  
  
  
  
  
  
  def 			lowercase__  (				A_:	int     ,			A_:	int		)  ->							tuple[int, int]:
  
  
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
         a ^= b
         b ^= a
         a ^= b
         return a, b
  
  
  
  
  
  
  
  def 			lowercase__  (				A_:	int     ,			A_:	list[list[int]]		)  ->							list[list[int]]:
  
  
  
  
  
  
  
         """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_:	int     ,			A_:	int     ,			A_:	list[int]     ,			A_:	list[list[int]]		)  ->							int:
  
  
  
  
  
  
  
         """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_:	list[int]     ,			A_:	list[list[int]]     ,			A_:	int     ,			A_:	dict[int, list[int]]     ,			A_:	int = 1     ,			)  ->							tuple[list[int], list[list[int]]]:
  
  
  
  
  
  
  
         """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__  (				)  ->							None:
  
  
  
  
  
  
  
         """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: 
  
  
  
  
  
  
  from __future__ import annotations
  
  __A  							=  [2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]
  
  
  
  class 							_A :
      """simple docstring"""
  
      def __init__(							self			:    List[str]   ,    __SCREAMING_SNAKE_CASE			:    int			)			->       None:
             __UpperCAmelCase    							=-1
             __UpperCAmelCase    							=-1
             __UpperCAmelCase    							=[-1] * length
             __UpperCAmelCase    							=None
             __UpperCAmelCase    							=None
  
  
  
      def __repr__(							self			:    Optional[int]			)			->       str:
             return f'''Node(min_value={self.minn} max_value={self.maxx})'''
  
  
  
  
  
  
  
  def 			lowercase__  (				A_:	list[int]		)  ->							Node | None:
  
  
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
         __UpperCAmelCase    							=Node(len(A_		)		)
         __UpperCAmelCase							,   __UpperCAmelCase    							=min(A_		), max(A_		)
         # Leaf node case where the node contains only one unique value
         if root.minn == root.maxx:
                return root
         __UpperCAmelCase    							=(root.minn + root.maxx) // 2
  
         __UpperCAmelCase    							=[]
         __UpperCAmelCase    							=[]
  
         for index, num in enumerate(A_		):
                if num <= pivot:
                       left_arr.append(A_		)
                else:
                       right_arr.append(A_		)
                __UpperCAmelCase    							=len(A_		)
         __UpperCAmelCase    							=build_tree(A_		)
         __UpperCAmelCase    							=build_tree(A_		)
         return root
  
  
  
  
  
  
  
  def 			lowercase__  (				A_:	Node | None     ,			A_:	int     ,			A_:	int		)  ->							int:
  
  
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
         if index < 0 or node is None:
                return 0
         # Leaf node cases
         if node.minn == node.maxx:
                return index + 1 if node.minn == num else 0
         __UpperCAmelCase    							=(node.minn + node.maxx) // 2
         if num <= pivot:
                # go the left subtree and map index to the left subtree
                return rank_till_index(node.left     ,			A_     ,			node.map_left[index] - 1		)
         else:
                # go to the right subtree and map index to the right subtree
                return rank_till_index(node.right     ,			A_     ,			index - node.map_left[index]		)
  
  
  
  
  
  
  
  def 			lowercase__  (				A_:	Node | None     ,			A_:	int     ,			A_:	int     ,			A_:	int		)  ->							int:
  
  
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
         if start > end:
                return 0
         __UpperCAmelCase    							=rank_till_index(A_     ,			A_     ,			A_		)
         __UpperCAmelCase    							=rank_till_index(A_     ,			A_     ,			start - 1		)
         return rank_till_end - rank_before_start
  
  
  
  
  
  
  
  def 			lowercase__  (				A_:	Node | None     ,			A_:	int     ,			A_:	int     ,			A_:	int		)  ->							int:
  
  
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
         if index > (end - start) or start > end or node is None:
                return -1
         # Leaf node case
         if node.minn == node.maxx:
                return node.minn
         # Number of elements in the left subtree in interval [start, end]
         __UpperCAmelCase    							=node.map_left[end] - (
             node.map_left[start - 1] if start else 0
         )
         if num_elements_in_left_tree > index:
                return quantile(
                    node.left     ,			A_     ,			(node.map_left[start - 1] if start else 0)     ,			node.map_left[end] - 1     ,			)
         else:
                return quantile(
                    node.right     ,			index - num_elements_in_left_tree     ,			start - (node.map_left[start - 1] if start else 0)     ,			end - node.map_left[end]     ,			)
  
  
  
  
  
  
  
  def 			lowercase__  (				A_:	Node | None     ,			A_:	int     ,			A_:	int     ,			A_:	int     ,			A_:	int		)  ->							int:
  
  
  
  
  
  
  
         """simple docstring"""
  
  
  
  
  
  
         if (
             start > end
             or node is None
             or start_num > end_num
             or node.minn > end_num
             or node.maxx < start_num
         ):
                return 0
         if start_num <= node.minn and node.maxx <= end_num:
                return end - start + 1
         __UpperCAmelCase    							=range_counting(
             node.left     ,			(node.map_left[start - 1] if start else 0)     ,			node.map_left[end] - 1     ,			A_     ,			A_     ,			)
         __UpperCAmelCase    							=range_counting(
             node.right     ,			start - (node.map_left[start - 1] if start else 0)     ,			end - node.map_left[end]     ,			A_     ,			A_     ,			)
         return left + right
  
  
  if __name__ == "__main__":
     import doctest
  
     doctest.testmod()
  
  
  
  
  