

"""simple docstring"""
from __future__ import annotations

from queue import Queue




def 				a__	(	lowerCAmelCase ,  lowerCAmelCase						)  ->   tuple[int, int]:
      a ^= b
      b ^= a
      a ^= b
      return a, b




def 				a__	(	lowerCAmelCase ,  lowerCAmelCase						)  ->   list[list[int]]:
      UpperCAmelCase__ :       str						=						1
      while (1 << j) < max_node:
            for i in range(1 ,  max_node + 1						):
                  UpperCAmelCase__ :       List[str]						=						parent[j - 1][parent[j - 1][i]]
            j += 1
      return parent




def 				a__	(	lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase						)  ->   int:
      # u must be deeper in the tree than v
      if level[u] < level[v]:
            UpperCAmelCase__				,		UpperCAmelCase__ :       Optional[Any]						=						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__ :       str						=						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__ :       int						=						parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
      return parent[0][u]




def 				a__	(	lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase = 1 ,  )  ->   tuple[list[int], list[list[int]]]:
      UpperCAmelCase__ :       Any						=						0
      UpperCAmelCase__ :       Queue[int]						=						Queue(maxsize=lowerCAmelCase						)
      q.put(lowerCAmelCase						)
      while q.qsize() != 0:
            UpperCAmelCase__ :       Tuple						=						q.get()
            for v in graph[u]:
                  if level[v] == -1:
                        UpperCAmelCase__ :       Tuple						=						level[u] + 1
                        q.put(lowerCAmelCase						)
                        UpperCAmelCase__ :       Union[str, Any]						=						u
      return level, parent




def 				a__	(	)  ->   None:
      UpperCAmelCase__ :       List[str]						=						13
      # initializing with 0
      UpperCAmelCase__ :       int						=						[[0 for _ in range(max_node + 10						)] for _ in range(20						)]
      # initializing with -1 which means every node is unvisited
      UpperCAmelCase__ :       Optional[int]						=						[-1 for _ in range(max_node + 10						)]
      UpperCAmelCase__ :       dict[int, list[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__ :       Optional[Any]						=						breadth_first_search(lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase ,  lowerCAmelCase ,  1						)
      UpperCAmelCase__ :       List[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()




"""simple docstring"""
from __future__ import annotations




def 				a__	(	lowerCAmelCase						)  ->   set[int]:
      UpperCAmelCase__ :       List[Any]						=						{1}
      UpperCAmelCase__ :       Optional[int]						=						[1]
      for _ in range(2 ,  depth + 1						):
            UpperCAmelCase__ :       Tuple						=						[*previous_coefficients, 0]
            UpperCAmelCase__ :       List[str]						=						[0, *previous_coefficients]
            UpperCAmelCase__ :       Dict						=						[]
            for x, y in zip(lowerCAmelCase ,  lowerCAmelCase						):
                  coefficients.add(x + y						)
                  previous_coefficients.append(x + y						)
      return coefficients




def 				a__	(	lowerCAmelCase						)  ->   set[int]:
      UpperCAmelCase__ :       List[str]						=						set()
      for number in unique_coefficients:
            UpperCAmelCase__ :       int						=						2
            UpperCAmelCase__ :       List[Any]						=						number
            while divisor**2 <= copy_number:
                  UpperCAmelCase__ :       Tuple						=						0
                  while copy_number % divisor == 0:
                        copy_number //= divisor
                        multiplicity += 1
                  if multiplicity >= 2:
                        non_squarefrees.add(lowerCAmelCase						)
                        break
                  divisor += 1

      return unique_coefficients.difference(lowerCAmelCase						)




def 				a__	(	lowerCAmelCase = 51						)  ->   int:
      UpperCAmelCase__ :       Any						=						get_pascal_triangle_unique_coefficients(lowerCAmelCase						)
      UpperCAmelCase__ :       Dict						=						get_squarefrees(lowerCAmelCase						)
      return sum(lowerCAmelCase						)


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

