




from __future__ import annotations

from queue import Queue

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

def 					A				(				_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )     ->			list[list[int]]:
       lowerCamelCase       :				Optional[int]      			= 1
       while (1 << j) < max_node:
              for i in range(1			,max_node + 1   ):
                     lowerCamelCase       :				List[str]      			= parent[j - 1][parent[j - 1][i]]
              j += 1
       return parent

def 					A				(				_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )     ->			int:
       # u must be deeper in the tree than v
       if level[u] < level[v]:
              lowerCamelCase			,				lowerCamelCase       :				List[str]      			= swap(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )
       # making depth of u same as depth of v
       for i in range(18			,-1			,-1   ):
              if level[u] - (1 << i) >= level[v]:
                     lowerCamelCase       :				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]]:
                     lowerCamelCase			,				lowerCamelCase       :				Union[str, Any]      			= parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
       return parent[0][u]

def 					A				(				_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE = 1			,)     ->			tuple[list[int], list[list[int]]]:
       lowerCamelCase       :				Tuple      			= 0
       lowerCamelCase       :				Queue[int]      			= Queue(maxsize=_SCREAMING_SNAKE_CASE   )
       q.put(_SCREAMING_SNAKE_CASE   )
       while q.qsize() != 0:
              lowerCamelCase       :				Optional[int]      			= q.get()
              for v in graph[u]:
                     if level[v] == -1:
                            lowerCamelCase       :				int      			= level[u] + 1
                            q.put(_SCREAMING_SNAKE_CASE   )
                            lowerCamelCase       :				int      			= u
       return level, parent

def 					A				(				)     ->			None:
       lowerCamelCase       :				str      			= 13
       # initializing with 0
       lowerCamelCase       :				Optional[int]      			= [[0 for _ in range(max_node + 10   )] for _ in range(20   )]
       # initializing with -1 which means every node is unvisited
       lowerCamelCase       :				Optional[int]      			= [-1 for _ in range(max_node + 10   )]
       lowerCamelCase       :				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: [],
       }
       lowerCamelCase			,				lowerCamelCase       :				List[str]      			= breadth_first_search(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,1   )
       lowerCamelCase       :				Tuple      			= create_sparse(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )
       print("LCA of node 1 and 3 is: "			,lowest_common_ancestor(1			,3			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )   )
       print("LCA of node 5 and 6 is: "			,lowest_common_ancestor(5			,6			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )   )
       print("LCA of node 7 and 11 is: "			,lowest_common_ancestor(7			,11			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )   )
       print("LCA of node 6 and 7 is: "			,lowest_common_ancestor(6			,7			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )   )
       print("LCA of node 4 and 12 is: "			,lowest_common_ancestor(4			,12			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )   )
       print("LCA of node 8 and 8 is: "			,lowest_common_ancestor(8			,8			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )   )


if __name__ == "__main__":
       main()












import numpy as np

def 					A				(				_SCREAMING_SNAKE_CASE   )     ->			str:
       lowerCamelCase			,				lowerCamelCase       :				Dict      			= a.shape
       lowerCamelCase       :				Union[str, Any]      			= min(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE   )
       lowerCamelCase       :				Union[str, Any]      			= np.eye(_SCREAMING_SNAKE_CASE   )
       lowerCamelCase       :				List[Any]      			= a.copy()

       for k in range(t - 1   ):
              # select a column of modified matrix A':
              lowerCamelCase       :				Optional[Any]      			= r[k:, [k]]
              # construct first basis vector
              lowerCamelCase       :				Union[str, Any]      			= np.zeros_like(_SCREAMING_SNAKE_CASE   )
              lowerCamelCase       :				int      			= 1.0
              # determine scaling factor
              lowerCamelCase       :				Any      			= np.linalg.norm(_SCREAMING_SNAKE_CASE   )
              # construct vector v for Householder reflection
              lowerCamelCase       :				List[str]      			= x + np.sign(x[0]   ) * alpha * ea
              v /= np.linalg.norm(_SCREAMING_SNAKE_CASE   )

              # construct the Householder matrix
              lowerCamelCase       :				List[Any]      			= np.eye(m - k   ) - 2.0 * v @ v.T
              # pad with ones and zeros as necessary
              lowerCamelCase       :				Union[str, Any]      			= np.block([[np.eye(_SCREAMING_SNAKE_CASE   ), np.zeros((k, m - k)   )], [np.zeros((m - k, k)   ), q_k]]   )

              lowerCamelCase       :				Any      			= q @ q_k.T
              lowerCamelCase       :				List[Any]      			= q_k @ r

       return q, r


if __name__ == "__main__":
       import doctest

       doctest.testmod()






