



from __future__ import annotations

from queue import Queue
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						int  ,					_SCREAMING_SNAKE_CASE :						int					)->tuple[int, int]:
      a ^= b
      b ^= a
      a ^= b
      return a, b
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						int  ,					_SCREAMING_SNAKE_CASE :						list[list[int]]					)->list[list[int]]:
      _lowerCAmelCase			      =	1
      while (1 << j) < max_node:
            for i in range(1  ,					max_node + 1					):
                  _lowerCAmelCase			      =	parent[j - 1][parent[j - 1][i]]
            j += 1
      return parent
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						int  ,					_SCREAMING_SNAKE_CASE :						int  ,					_SCREAMING_SNAKE_CASE :						list[int]  ,					_SCREAMING_SNAKE_CASE :						list[list[int]]					)->int:
      # u must be deeper in the tree than v
      if level[u] < level[v]:
            _lowerCAmelCase      , _lowerCAmelCase			      =	swap(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)
      # making depth of u same as depth of v
      for i in range(1_8  ,					-1  ,					-1					):
            if level[u] - (1 << i) >= level[v]:
                  _lowerCAmelCase			      =	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(1_8  ,					-1  ,					-1					):
            if parent[i][u] not in [0, parent[i][v]]:
                  _lowerCAmelCase      , _lowerCAmelCase			      =	parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
      return parent[0][u]
def 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						list[int]  ,					_SCREAMING_SNAKE_CASE :						list[list[int]]  ,					_SCREAMING_SNAKE_CASE :						int  ,					_SCREAMING_SNAKE_CASE :						dict[int, list[int]]  ,					_SCREAMING_SNAKE_CASE :						int = 1  ,					)->tuple[list[int], list[list[int]]]:
      _lowerCAmelCase			      =	0
      _lowerCAmelCase			      =	Queue(maxsize=_SCREAMING_SNAKE_CASE					)
      q.put(_SCREAMING_SNAKE_CASE					)
      while q.qsize() != 0:
            _lowerCAmelCase			      =	q.get()
            for v in graph[u]:
                  if level[v] == -1:
                        _lowerCAmelCase			      =	level[u] + 1
                        q.put(_SCREAMING_SNAKE_CASE					)
                        _lowerCAmelCase			      =	u
      return level, parent
def 				UpperCAmelCase__		(					)->None:
      _lowerCAmelCase			      =	1_3
      # initializing with 0
      _lowerCAmelCase			      =	[[0 for _ in range(max_node + 1_0					)] for _ in range(2_0					)]
      # initializing with -1 which means every node is unvisited
      _lowerCAmelCase			      =	[-1 for _ in range(max_node + 1_0					)]
      _lowerCAmelCase			      =	{
          1: [2, 3, 4],
          2: [5],
          3: [6, 7],
          4: [8],
          5: [9, 1_0],
          6: [1_1],
          7: [],
          8: [1_2, 1_3],
          9: [],
          1_0: [],
          1_1: [],
          1_2: [],
          1_3: [],
      }
      _lowerCAmelCase      , _lowerCAmelCase			      =	breadth_first_search(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE  ,					1					)
      _lowerCAmelCase			      =	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  ,					1_1  ,					_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  ,					1_2  ,					_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 				UpperCAmelCase__		(					_SCREAMING_SNAKE_CASE :						Tuple					)->Union[str, Any]:
      _lowerCAmelCase      , _lowerCAmelCase			      =	a.shape
      _lowerCAmelCase			      =	min(_SCREAMING_SNAKE_CASE  ,					_SCREAMING_SNAKE_CASE					)
      _lowerCAmelCase			      =	np.eye(_SCREAMING_SNAKE_CASE					)
      _lowerCAmelCase			      =	a.copy()

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

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

            _lowerCAmelCase			      =	q @ q_k.T
            _lowerCAmelCase			      =	q_k @ r

      return q, r


if __name__ == "__main__":
    import doctest

    doctest.testmod()