






"""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 unittest

from transformers import is_torch_available, load_tool

from .test_tools_common import ToolTesterMixin


if is_torch_available():
						import torch



class        lowercase    (	unittest.TestCase,       a_			):


							def     _snake_case				(      self)				->					Optional[int]:
								UpperCAmelCase_		:   int													=       load_tool('speech-to-text')
								self.tool.setup()


							def     _snake_case				(      self)				->					Any:
								UpperCAmelCase_		:   str													=       self.tool(torch.ones(3000))
								self.assertEqual(_snake_case     ,      ' you')





							def     _snake_case				(      self)				->					str:
								UpperCAmelCase_		:   List[Any]													=       self.tool(audio=torch.ones(3000))
								self.assertEqual(_snake_case     ,      ' you')






