"""simple docstring"""


import enum
import inspect
import warnings
from functools import wraps
from typing import Callable, Optional

from .logging import get_logger


__UpperCamelCase								=    set()
__UpperCamelCase								=    get_logger(__name__)







def       UpperCAmelCase					(	UpperCAmelCase = None      )       ->   int:

     def decorator(UpperCAmelCase      ):
          global _emitted_deprecation_warnings

          if inspect.isclass(UpperCAmelCase      ):
               snake_case_       =      deprecated_class_or_function.__init__
               snake_case_       =      deprecated_class_or_function.__name__
          else:
               snake_case_       =      deprecated_class_or_function
               snake_case_       =      deprecated_function.__name__
               # Support deprecating __init__ class method: class name instead
               snake_case_       =      name if name != '__init__' else deprecated_function.__qualname__.split('.'      )[-2]

          snake_case_       =      (
              f'{name} is deprecated and will be removed in the next major version of datasets.' + f' {help_message}'
              if help_message
              else ''
          )

          @wraps(UpperCAmelCase      )
          def wrapper(*UpperCAmelCase		,      **UpperCAmelCase      ):
               snake_case_       =      hash(UpperCAmelCase      )
               if func_hash not in _emitted_deprecation_warnings:
                    warnings.warn(UpperCAmelCase		,      category=UpperCAmelCase		,      stacklevel=2      )
                    _emitted_deprecation_warnings.add(UpperCAmelCase      )
               return deprecated_function(*UpperCAmelCase		,      **UpperCAmelCase      )

          snake_case_       =      'deprecated'

          if inspect.isclass(UpperCAmelCase      ):
               snake_case_       =      wrapper
               return deprecated_class_or_function
          else:
               return wrapper

     return decorator




class 				UpperCamelCase      (       enum.EnumMeta     ):







       def __getattribute__(				cls,							lowerCAmelCase__)   ->   List[Any]:
            snake_case_       =      super().__getattribute__(lowerCAmelCase__)
            if isinstance(lowerCAmelCase__,							enum.Enum) and obj._on_access:
                 obj._on_access()
            return obj







       def __getitem__(				cls,							lowerCAmelCase__)   ->   str:
            snake_case_       =      super().__getitem__(lowerCAmelCase__)
            if member._on_access:
                 member._on_access()
            return member







       def __call__(				cls,							lowerCAmelCase__,							lowerCAmelCase__=None,							*, lowerCAmelCase__=None,							lowerCAmelCase__=None,							lowerCAmelCase__=None,							lowerCAmelCase__=1)   ->   Union[str, Any]:
            snake_case_       =      super().__call__(lowerCAmelCase__,							lowerCAmelCase__,							module=lowerCAmelCase__,							qualname=lowerCAmelCase__,							type=lowerCAmelCase__,							start=lowerCAmelCase__)
            if isinstance(lowerCAmelCase__,							enum.Enum) and obj._on_access:
                 obj._on_access()
            return obj




class 				UpperCamelCase      (       enum.Enum					,	metaclass=lowerCAmelCase__     ):







       def __new__(				cls,							lowerCAmelCase__)   ->   List[Any]:
            snake_case_       =      object.__new__(cls)
            snake_case_       =      value
            snake_case_       =      member.deprecate
            return member







       @property
       def 	a_		(				self)   ->   List[Any]:
            return ""







       def 	a_		(				self)   ->   Optional[Any]:
            snake_case_       =      f' {self.help_message}' if self.help_message else ''
            warnings.warn(
                f'\'{self.__objclass__.__name__}\' is deprecated and will be removed in the next major version of datasets.'
                + help_message,							lowerCAmelCase__,							stacklevel=3,							)


"""simple docstring"""


from __future__ import annotations

from queue import Queue







def       UpperCAmelCase					(	UpperCAmelCase		,      UpperCAmelCase      )       ->   tuple[int, int]:
     a ^= b
     b ^= a
     a ^= b
     return a, b







def       UpperCAmelCase					(	UpperCAmelCase		,      UpperCAmelCase      )       ->   list[list[int]]:
     snake_case_       =      1
     while (1 << j) < max_node:
          for i in range(1		,      max_node + 1      ):
               snake_case_       =      parent[j - 1][parent[j - 1][i]]
          j += 1
     return parent







def       UpperCAmelCase					(	UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase      )       ->   int:
     # u must be deeper in the tree than v
     if level[u] < level[v]:
          snake_case_ ,			snake_case_       =      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]:
               snake_case_       =      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]]:
               snake_case_ ,			snake_case_       =      parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
     return parent[0][u]







def       UpperCAmelCase					(	UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase = 1		,      )       ->   tuple[list[int], list[list[int]]]:
     snake_case_       =      0
     snake_case_       =      Queue(maxsize=UpperCAmelCase      )
     q.put(UpperCAmelCase      )
     while q.qsize() != 0:
          snake_case_       =      q.get()
          for v in graph[u]:
               if level[v] == -1:
                    snake_case_       =      level[u] + 1
                    q.put(UpperCAmelCase      )
                    snake_case_       =      u
     return level, parent







def       UpperCAmelCase					(	)       ->   None:
     snake_case_       =      13
     # initializing with 0
     snake_case_       =      [[0 for _ in range(max_node + 10      )] for _ in range(20      )]
     # initializing with -1 which means every node is unvisited
     snake_case_       =      [-1 for _ in range(max_node + 10      )]
     snake_case_       =      {
         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: [],
     }
     snake_case_ ,			snake_case_       =      breadth_first_search(UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      UpperCAmelCase		,      1      )
     snake_case_       =      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()

