






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()




def   _lowerCAmelCase(						):

  for a in range(300      ):
    for b in range(a + 1 ,							400      ):
      for c in range(b + 1 ,							500      ):
        if (a + b + c) == 1000 and (a**2) + (b**2) == (c**2):
          return a * b * c

  return -1
def   _lowerCAmelCase(						):

  for a in range(300      ):
    for b in range(400      ):
      UpperCAmelCase          =	1000 - a - b
      if a < b < c and (a**2) + (b**2) == (c**2):
        return a * b * c

  return -1
def   _lowerCAmelCase(						):
  import timeit

  print(
      timeit.timeit("solution()" ,							setup="from __main__ import solution" ,							number=1000      )      )
  print(
      timeit.timeit(
          "solution_fast()" ,							setup="from __main__ import solution_fast" ,							number=1000      )      )


if __name__ == "__main__":
      print(f"{solution() = }")



