




from collections import OrderedDict
from dataclasses import fields
from typing import Any, Tuple

import numpy as np

from .import_utils import is_torch_available




def        __SCREAMING_SNAKE_CASE (	lowercase_   )							->						Dict:

    """simple docstring"""


    if is_torch_available():
        import torch

        if isinstance(lowercase_       ,  torch.Tensor   ):
            return True

    return isinstance(lowercase_       ,  np.ndarray   )


class 			_lowerCamelCase    (      _SCREAMING_SNAKE_CASE ):

      """simple docstring"""

      def    snake_case						(  self       :			Optional[Any]					):
          __UpperCamelCase			=    fields(self					)

          # Safety and consistency checks
          if not len(snake_case					):
              raise ValueError(F"{self.__class__.__name__} has no fields."					)

          __UpperCamelCase			=    getattr(self			,							class_fields[0].name					)
          __UpperCamelCase			=    all(getattr(self			,							field.name					) is None for field in class_fields[1:]					)

          if other_fields_are_none and isinstance(snake_case			,							snake_case					):
              for key, value in first_field.items():
                  __UpperCamelCase			=    value
          else:
              for field in class_fields:
                  __UpperCamelCase			=    getattr(self			,							field.name					)
                  if v is not None:
                      __UpperCamelCase			=    v







      def __delitem__(  self       :			Union[str, Any]			,							*snake_case       :			List[str]			,							**snake_case       :			List[str]					):
          raise Exception(F"You cannot use ``__delitem__`` on a {self.__class__.__name__} instance."					)







      def    snake_case						(  self       :			List[Any]			,							*snake_case       :			Optional[int]			,							**snake_case       :			Tuple					):
          raise Exception(F"You cannot use ``setdefault`` on a {self.__class__.__name__} instance."					)







      def    snake_case						(  self       :			Optional[int]			,							*snake_case       :			Union[str, Any]			,							**snake_case       :			str					):
          raise Exception(F"You cannot use ``pop`` on a {self.__class__.__name__} instance."					)







      def    snake_case						(  self       :			Any			,							*snake_case       :			Optional[Any]			,							**snake_case       :			int					):
          raise Exception(F"You cannot use ``update`` on a {self.__class__.__name__} instance."					)







      def __getitem__(  self       :			str			,							snake_case       :			List[str]					):
          if isinstance(snake_case			,							snake_case					):
              __UpperCamelCase			=    dict(self.items()					)
              return inner_dict[k]
          else:
              return self.to_tuple()[k]







      def __setattr__(  self       :			Dict			,							snake_case       :			List[Any]			,							snake_case       :			List[Any]					):
          if name in self.keys() and value is not None:
              # Don't call self.__setitem__ to avoid recursion errors
              super().__setitem__(snake_case			,							snake_case					)
          super().__setattr__(snake_case			,							snake_case					)







      def __setitem__(  self       :			Dict			,							snake_case       :			Optional[Any]			,							snake_case       :			Optional[Any]					):
          # Will raise a KeyException if needed
          super().__setitem__(snake_case			,							snake_case					)
          # Don't call self.__setattr__ to avoid recursion errors
          super().__setattr__(snake_case			,							snake_case					)







      def    snake_case						(  self       :			Any					):
          return tuple(self[k] for k in self.keys()					)













"""simple docstring"""
from __future__ import annotations

from queue import Queue






def    A__							(     UpperCamelCase   ,    UpperCamelCase			):
							a ^= b
							b ^= a
							a ^= b
							return a, b






def    A__							(     UpperCamelCase   ,    UpperCamelCase			):
							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    A__							(     UpperCamelCase   ,    UpperCamelCase   ,    UpperCamelCase   ,    UpperCamelCase			):
							# u must be deeper in the tree than v
							if level[u] < level[v]:
														A,      A						=    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]:
																					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(18   ,    -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    A__							(     UpperCamelCase   ,    UpperCamelCase   ,    UpperCamelCase   ,    UpperCamelCase   ,    UpperCamelCase = 1   ,    ):
							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    A__							(     ):
							A						=    13
							# initializing with 0
							A						=    [[0 for _ in range(max_node + 10			)] for _ in range(20			)]
							# initializing with -1 which means every node is unvisited
							A						=    [-1 for _ in range(max_node + 10			)]
							A						=    {
							    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: [],
							}
							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   ,    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()


