






"""simple docstring"""


from __future__ import annotations

from queue import Queue



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  a ^= b
  b ^= a
  a ^= b
  return a, b



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """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    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  if level[u] < level[v]:
    __A     ,       __A		     =					swap(__UpperCamelCase						,			__UpperCamelCase					)
  # making depth of u same as depth of v
  for i in range(1_8						,			-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(1_8						,			-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    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase = 1						,			):




  """simple docstring"""







  __A		     =					0
  __A		     =					Queue(maxsize=__UpperCamelCase					)
  q.put(__UpperCamelCase					)
  while q.qsize() != 0:
    __A		     =					q.get()
    for v in graph[u]:
      if level[v] == -1:
        __A		     =					level[u] + 1
        q.put(__UpperCamelCase					)
        __A		     =					u
  return level, parent



def    lowerCAmelCase							(       ):




  """simple docstring"""







  __A		     =					1_3
  # initializing with 0
  __A		     =					[[0 for _ in range(max_node + 1_0					)] for _ in range(2_0					)]
  # initializing with -1 which means every node is unvisited
  __A		     =					[-1 for _ in range(max_node + 1_0					)]
  __A		     =					{
      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: [],
  }
  __A     ,       __A		     =					breadth_first_search(__UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase						,			__UpperCamelCase						,			1					)
  __A		     =					create_sparse(__UpperCamelCase						,			__UpperCamelCase					)
  print('''LCA of node 1 and 3 is: '''						,			lowest_common_ancestor(1						,			3						,			__UpperCamelCase						,			__UpperCamelCase					)					)
  print('''LCA of node 5 and 6 is: '''						,			lowest_common_ancestor(5						,			6						,			__UpperCamelCase						,			__UpperCamelCase					)					)
  print('''LCA of node 7 and 11 is: '''						,			lowest_common_ancestor(7						,			1_1						,			__UpperCamelCase						,			__UpperCamelCase					)					)
  print('''LCA of node 6 and 7 is: '''						,			lowest_common_ancestor(6						,			7						,			__UpperCamelCase						,			__UpperCamelCase					)					)
  print('''LCA of node 4 and 12 is: '''						,			lowest_common_ancestor(4						,			1_2						,			__UpperCamelCase						,			__UpperCamelCase					)					)
  print('''LCA of node 8 and 8 is: '''						,			lowest_common_ancestor(8						,			8						,			__UpperCamelCase						,			__UpperCamelCase					)					)


if __name__ == "__main__":
       main()








"""simple docstring"""





import math as m


def   _snake_case    (    _snake_case					:      List[Any]			, _snake_case					:      Tuple			, _snake_case					:      Tuple=0.001      ):
      return (f(a + h      ) - f(a - h      )) / (2 * h)


def   _snake_case    (    _snake_case					:      int			, _snake_case					:      List[Any]=0			, _snake_case					:      Any=100			, _snake_case					:      Any=0.0001			, _snake_case					:      Optional[Any]=1E-6			, _snake_case					:      Any=False      ):
      lowerCAmelCase       :						Optional[Any]							= xa  # set the initial guess
      lowerCAmelCase       :						str							= [a]
      lowerCAmelCase       :						List[str]							= abs(f(_snake_case      )      )
      lowerCAmelCase       :						Dict							= lambda _snake_case      : calc_derivative(_snake_case			, _snake_case			, h=_snake_case      )  # noqa: E731  Derivative of f(x)
      for _ in range(_snake_case      ):
            if fa(_snake_case      ) == 0:
                  raise ValueError('''No converging solution found'''      )
            lowerCAmelCase       :						Tuple							= a - f(_snake_case      ) / fa(_snake_case      )  # Calculate the next estimate
            if logsteps:
                  steps.append(_snake_case      )
            if error < maxerror:
                  break
      else:
            raise ValueError('''Iteration limit reached, no converging solution found'''      )
      if logsteps:
            # If logstep is true, then log intermediate steps
            return a, error, steps
      return a, error


if __name__ == "__main__":
 from matplotlib import pyplot as plt

 snake_case__		:  Any     					=					lambda x: m.tanh(x) ** 2 - m.exp(3 * x)  # noqa: E731
 snake_case__					,  snake_case__					,  snake_case__		:  List[str]     					=					newton_raphson(
     f, xa=10, maxiter=1_000, step=1e-6, logsteps=True
 )
 plt.plot([abs(f(x)) for x in steps])
 plt.xlabel('''step''')
 plt.ylabel('''error''')
 plt.show()
 print(f"""solution = {{{solution:f}}}, error = {{{error:f}}}""")


