






"""simple docstring"""



from __future__ import annotations

from queue import Queue
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    int						,   __snake_case     :    int       ):





  '''simple docstring'''





  a ^= b
  b ^= a
  a ^= b
  return a, b
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    int						,   __snake_case     :    list[list[int]]       ):





  '''simple docstring'''





  lowercase				       =			1
  while (1 << j) < max_node:
    for i in range(1						,   max_node + 1       ):
      lowercase				       =			parent[j - 1][parent[j - 1][i]]
    j += 1
  return parent
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    int						,   __snake_case     :    int						,   __snake_case     :    list[int]						,   __snake_case     :    list[list[int]]       ):





  '''simple docstring'''





  if level[u] < level[v]:
    lowercase       ,	lowercase				       =			swap(__snake_case						,   __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]:
      lowercase				       =			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]]:
      lowercase       ,	lowercase				       =			parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
  return parent[0][u]
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    list[int]						,   __snake_case     :    list[list[int]]						,   __snake_case     :    int						,   __snake_case     :    dict[int, list[int]]						,   __snake_case     :    int = 1						,   ):





  '''simple docstring'''





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





  '''simple docstring'''





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


if __name__ == "__main__":
    main()






from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


__UpperCAmelCase      			=  {"""configuration_sew_d""": ["""SEW_D_PRETRAINED_CONFIG_ARCHIVE_MAP""", """SEWDConfig"""]}

try:
     if not is_torch_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     __UpperCAmelCase      			=  [
         """SEW_D_PRETRAINED_MODEL_ARCHIVE_LIST""",
         """SEWDForCTC""",
         """SEWDForSequenceClassification""",
         """SEWDModel""",
         """SEWDPreTrainedModel""",
     ]

if TYPE_CHECKING:
     from .configuration_sew_d import SEW_D_PRETRAINED_CONFIG_ARCHIVE_MAP, SEWDConfig

     try:
          if not is_torch_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .modeling_sew_d import (
              SEW_D_PRETRAINED_MODEL_ARCHIVE_LIST,
              SEWDForCTC,
              SEWDForSequenceClassification,
              SEWDModel,
              SEWDPreTrainedModel,
          )


else:
     import sys

     __UpperCAmelCase      			=  _LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)

