
'''simple docstring'''

from __future__ import annotations

from queue import Queue







def __A  (    lowerCAmelCase_ ,       lowerCAmelCase_       ):
     a ^= b
     b ^= a
     a ^= b
     return a, b







def __A  (    lowerCAmelCase_ ,       lowerCAmelCase_       ):
     _UpperCAmelCase					:  Optional[Any]         =    1
     while (1 << j) < max_node:
          for i in range(1 ,       max_node + 1       ):
               _UpperCAmelCase					:  Tuple         =    parent[j - 1][parent[j - 1][i]]
          j += 1
     return parent







def __A  (    lowerCAmelCase_ ,       lowerCAmelCase_ ,       lowerCAmelCase_ ,       lowerCAmelCase_       ):
     # 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					:  Optional[Any]         =    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					:  List[str]         =    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 ,       ):
     _UpperCAmelCase					:  int         =    0
     _UpperCAmelCase					:  Queue[int]         =    Queue(maxsize=lowerCAmelCase_       )
     q.put(lowerCAmelCase_       )
     while q.qsize() != 0:
          _UpperCAmelCase					:  List[str]         =    q.get()
          for v in graph[u]:
               if level[v] == -1:
                    _UpperCAmelCase					:  Union[str, Any]         =    level[u] + 1
                    q.put(lowerCAmelCase_       )
                    _UpperCAmelCase					:  Any         =    u
     return level, parent







def __A  (    ):
     _UpperCAmelCase					:  Optional[Any]         =    13
     # initializing with 0
     _UpperCAmelCase					:  Any         =    [[0 for _ in range(max_node + 10       )] for _ in range(20       )]
     # initializing with -1 which means every node is unvisited
     _UpperCAmelCase					:  Any         =    [-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					:  Tuple         =    breadth_first_search(lowerCAmelCase_ ,       lowerCAmelCase_ ,       lowerCAmelCase_ ,       lowerCAmelCase_ ,       1       )
     _UpperCAmelCase					:  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 itertools import combinations, product







def __A  (    lowerCAmelCase_ ,       lowerCAmelCase_ ,       lowerCAmelCase_ ,       lowerCAmelCase_       ):
     if xa == ya == 0 or xa == ya == 0:
          return False
     _UpperCAmelCase					:  Any         =    xa * xa + ya * ya
     _UpperCAmelCase					:  Any         =    xa * xa + ya * ya
     _UpperCAmelCase					:  Tuple         =    (xa - xa) * (xa - xa) + (ya - ya) * (ya - ya)
     return (
         a_square + b_square == c_square
         or a_square + c_square == b_square
         or b_square + c_square == a_square
     )







def __A  (    lowerCAmelCase_ = 50       ):
     return sum(
         1
         for pta, pta in combinations(product(range(limit + 1       ) ,       repeat=2       ) ,       2       )
         if is_right(*lowerCAmelCase_ ,       *lowerCAmelCase_       )       )


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


