code: 
  
  from __future__ import annotations
  
  from queue import Queue
  def 		SCREAMING_SNAKE_CASE__				(							_UpperCAmelCase,      _UpperCAmelCase				)					-> Dict:
  
  
  
      '''simple docstring'''
  
  
  
  
  
  
      a ^= b
      b ^= a
      a ^= b
      return a, b
  def 		SCREAMING_SNAKE_CASE__				(							_UpperCAmelCase,      _UpperCAmelCase				)					-> Union[str, Any]:
  
  
  
      '''simple docstring'''
  
  
  
  
  
  
      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 		SCREAMING_SNAKE_CASE__				(							_UpperCAmelCase,      _UpperCAmelCase,      _UpperCAmelCase,      _UpperCAmelCase				)					-> List[str]:
  
  
  
      '''simple docstring'''
  
  
  
  
  
  
      if level[u] < level[v]:
          lowerCAmelCase    			=      swap(UpperCamelCase__,      UpperCamelCase__				)
      # making depth of u same as depth of v
      for i in range(18,      -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(18,      -1,      -1				):
          if parent[i][u] not in [0, parent[i][v]]:
              lowerCAmelCase    			=      parent[i][u], parent[i][v]
      # returning longest common ancestor of u,v
      return parent[0][u]
  def 		SCREAMING_SNAKE_CASE__				(							_UpperCAmelCase,      _UpperCAmelCase,      _UpperCAmelCase,      _UpperCAmelCase,      _UpperCAmelCase = 1,      )					-> Dict:
  
  
  
      '''simple docstring'''
  
  
  
  
  
  
      lowerCAmelCase    			=      0
      lowerCAmelCase    			=      Queue(maxsize=UpperCamelCase__				)
      q.put(UpperCamelCase__				)
      while q.qsize() != 0:
          lowerCAmelCase    			=      q.get()
          for v in graph[u]:
              if level[v] == -1:
                  lowerCAmelCase    			=      level[u] + 1
                  q.put(UpperCamelCase__				)
                  lowerCAmelCase    			=      u
      return level, parent
  def 		SCREAMING_SNAKE_CASE__				(							)					-> Optional[Any]:
  
  
  
      '''simple docstring'''
  
  
  
  
  
  
      lowerCAmelCase    			=      13
      # initializing with 0
      lowerCAmelCase    			=      [[0 for _ in range(max_node + 10				)] for _ in range(20				)]
      # initializing with -1 which means every node is unvisited
      lowerCAmelCase    			=      [-1 for _ in range(max_node + 10				)]
      lowerCAmelCase    			=      {
          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    			=      breadth_first_search(UpperCamelCase__,      UpperCamelCase__,      UpperCamelCase__,      UpperCamelCase__,      1				)
      lowerCAmelCase    			=      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,      11,      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,      12,      UpperCamelCase__,      UpperCamelCase__				)				)
      print('LCA of node 8 and 8 is: ',      lowest_common_ancestor(8,      8,      UpperCamelCase__,      UpperCamelCase__				)				)
  
  
  if __name__ == "__main__":
   main()
  
  
  
  
  
  
style_context: 
  
  from typing import TYPE_CHECKING
  
  from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tokenizers_available, is_torch_available
  
  
  __A   :     Optional[int]      =			{
      '''configuration_splinter''': ['''SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''SplinterConfig'''],
      '''tokenization_splinter''': ['''SplinterTokenizer'''],
  }
  
  try:
   if not is_tokenizers_available():
    raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
   pass
  else:
   __A   :     Optional[int]      =			['''SplinterTokenizerFast''']
  
  try:
   if not is_torch_available():
    raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
   pass
  else:
   __A   :     Union[str, Any]      =			[
       '''SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST''',
       '''SplinterForQuestionAnswering''',
       '''SplinterForPreTraining''',
       '''SplinterLayer''',
       '''SplinterModel''',
       '''SplinterPreTrainedModel''',
   ]
  
  
  if TYPE_CHECKING:
   from .configuration_splinter import SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP, SplinterConfig
   from .tokenization_splinter import SplinterTokenizer
  
   try:
    if not is_tokenizers_available():
     raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
    pass
   else:
    from .tokenization_splinter_fast import SplinterTokenizerFast
  
   try:
    if not is_torch_available():
     raise OptionalDependencyNotAvailable()
   except OptionalDependencyNotAvailable:
    pass
   else:
    from .modeling_splinter import (
        SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST,
        SplinterForPreTraining,
        SplinterForQuestionAnswering,
        SplinterLayer,
        SplinterModel,
        SplinterPreTrainedModel,
    )
  
  
  else:
   import sys
  
   __A   :     Optional[Any]      =			_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)
  
  
  
  
  
  