






from __future__ import annotations

from queue import Queue



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

		a ^= b
		b ^= a
		a ^= b
		return a, b



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

		__A    =							1
		while (1 << j) < max_node:
				for i in range(1					,     max_node + 1	):
						__A    =							parent[j - 1][parent[j - 1][i]]
				j += 1
		return parent



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__	):


		'''simple docstring'''

		if level[u] < level[v]:
				__A ,   __A    =							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]:
						__A    =							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]]:
						__A ,   __A    =							parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
		return parent[0][u]



def      UpperCAmelCase						( lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__ = 1					,     ):


		'''simple docstring'''

		__A    =							0
		__A    =							Queue(maxsize=lowerCAmelCase__	)
		q.put(lowerCAmelCase__	)
		while q.qsize() != 0:
				__A    =							q.get()
				for v in graph[u]:
						if level[v] == -1:
								__A    =							level[u] + 1
								q.put(lowerCAmelCase__	)
								__A    =							u
		return level, parent



def      UpperCAmelCase						( ):


		'''simple docstring'''

		__A    =							13
		# initializing with 0
		__A    =							[[0 for _ in range(max_node + 10	)] for _ in range(20	)]
		# initializing with -1 which means every node is unvisited
		__A    =							[-1 for _ in range(max_node + 10	)]
		__A    =							{
		    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: [],
		}
		__A ,   __A    =							breadth_first_search(lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     lowerCAmelCase__					,     1	)
		__A    =							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"""





def     _A    (    UpperCamelCase_	:			int,     UpperCamelCase_	:			int = 1000)      ->		str:
   '''simple docstring'''


   if (not isinstance(UpperCamelCase_,     UpperCamelCase_)) or (digit_position <= 0):
      raise ValueError("Digit position must be a positive integer")
   elif (not isinstance(UpperCamelCase_,     UpperCamelCase_)) or (precision < 0):
      raise ValueError("Precision must be a nonnegative integer")

   # compute an approximation of (16 ** (n - 1)) * pi whose fractional part is mostly
   # accurate
   __lowercase								=		(
       4 * _subsum(UpperCamelCase_,     1,     UpperCamelCase_)
       - 2 * _subsum(UpperCamelCase_,     4,     UpperCamelCase_)
       - _subsum(UpperCamelCase_,     5,     UpperCamelCase_)
       - _subsum(UpperCamelCase_,     6,     UpperCamelCase_)
   )

   # return the first hex digit of the fractional part of the result
   return hex(int((sum_result % 1) * 16))[2:]




def     _A    (    UpperCamelCase_	:			int,     UpperCamelCase_	:			int,     UpperCamelCase_	:			int)      ->		float:
   '''simple docstring'''


   __lowercase								=		0.0
   for sum_index in range(digit_pos_to_extract + precision):
      __lowercase								=		8 * sum_index + denominator_addend
      if sum_index < digit_pos_to_extract:
         # if the exponential term is an integer and we mod it by the denominator
         # before dividing, only the integer part of the sum will change;
         # the fractional part will not
         __lowercase								=		pow(
             16,     digit_pos_to_extract - 1 - sum_index,     UpperCamelCase_)
      else:
         __lowercase								=		pow(16,     digit_pos_to_extract - 1 - sum_index)
      total += exponential_term / denominator
   return total


if __name__ == "__main__":
   import doctest

   doctest.testmod()




