

from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

lowerCamelCase           =					TypeVar('''T''')
lowerCamelCase           =					TypeVar('''U''')







class 						__magic_name__			(							Generic[T, U]							):

   '''simple docstring'''




   def __init__(				self,    lowercase_,    lowercase_       )							->    Dict:






     """simple docstring"""






     a__  =key
     a__  =val
     a__  =None
     a__  =None



   def __repr__(				self       )							->    str:






     """simple docstring"""






     return (
         F"""Node: key: {self.key}, val: {self.val}, """
         F"""has next: {bool(self.next       )}, has prev: {bool(self.prev       )}"""
     )







class 						__magic_name__			(							Generic[T, U]							):

   '''simple docstring'''




   def __init__(				self       )							->    None:






     """simple docstring"""






     a__  =DoubleLinkedListNode(lowercase_,    lowercase_       )
     a__  =DoubleLinkedListNode(lowercase_,    lowercase_       )
     a__,      a__  =self.rear, self.head



   def __repr__(				self       )							->    str:






     """simple docstring"""






     a__  =['''DoubleLinkedList''']
     a__  =self.head
     while node.next is not None:
       rep.append(str(lowercase_       )       )
       a__  =node.next
     rep.append(str(self.rear       )       )
     return ",\n    ".join(lowercase_       )



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






     a__  =self.rear.prev

     # All nodes other than self.head are guaranteed to have non-None previous
     assert previous is not None

     a__  =node
     a__  =previous
     a__  =node
     a__  =self.rear



   def  _UpperCAmelCase (				self,    lowercase_       )							->    DoubleLinkedListNode[T, U] | None:






     """simple docstring"""






     if node.prev is None or node.next is None:
       return None

     a__  =node.next
     a__  =node.prev
     a__  =None
     a__  =None
     return node







class 						__magic_name__			(							Generic[T, U]							):

   '''simple docstring'''




   lowerCamelCase__ :	dict[Callable[[T], U], LRUCache[T, U]]    =   {}



   def __init__(				self,    lowercase_       )							->    List[str]:






     """simple docstring"""






     a__  =DoubleLinkedList()
     a__  =capacity
     a__  =0
     a__  =0
     a__  =0
     a__  ={}



   def __repr__(				self       )							->    str:






     """simple docstring"""






     return (
         F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
         F"""capacity={self.capacity}, current size={self.num_keys})"""
     )



   def __contains__(				self,    lowercase_       )							->    bool:






     """simple docstring"""






     return key in self.cache



   def  _UpperCAmelCase (				self,    lowercase_       )							->    U | None:






     """simple docstring"""






     if key in self.cache:
       self.hits += 1
       a__  =self.cache[key]
       a__  =self.list.remove(self.cache[key]       )
       assert node == value_node

       # node is guaranteed not None because it is in self.cache
       assert node is not None
       self.list.add(lowercase_       )
       return node.val
     self.miss += 1
     return None



   def  _UpperCAmelCase (				self,    lowercase_,    lowercase_       )							->    None:






     """simple docstring"""






     if key not in self.cache:
       if self.num_keys >= self.capacity:
         # delete first node (oldest) when over capacity
         a__  =self.list.head.next

         # guaranteed to have a non-None first node when num_keys > 0
         # explain to type checker via assertions
         assert first_node is not None
         assert first_node.key is not None
         assert (
             self.list.remove(lowercase_       ) is not None
         )  # node guaranteed to be in list assert node.key is not None

         del self.cache[first_node.key]
         self.num_keys -= 1
       a__  =DoubleLinkedListNode(lowercase_,    lowercase_       )
       self.list.add(self.cache[key]       )
       self.num_keys += 1

     else:
       # bump node to the end of the list, update value
       a__  =self.list.remove(self.cache[key]       )
       assert node is not None  # node guaranteed to be in list
       a__  =value
       self.list.add(lowercase_       )



   @classmethod
   def  _UpperCAmelCase (				cls,    lowercase_ = 128       )							->    Callable[[Callable[[T], U]], Callable[..., U]]:






     """simple docstring"""






     def cache_decorator_inner(lowercase_       ) -> Callable[..., U]:
       def cache_decorator_wrapper(*lowercase_       ) -> U:
         if func not in cls.decorator_function_to_instance_map:
           a__  =LRUCache(lowercase_       )

         a__  =cls.decorator_function_to_instance_map[func].get(args[0]       )
         if result is None:
           a__  =func(*lowercase_       )
           cls.decorator_function_to_instance_map[func].put(args[0],    lowercase_       )
         return result

       def cache_info() -> LRUCache[T, U]:
         return cls.decorator_function_to_instance_map[func]

       setattr(lowercase_,    '''cache_info''',    lowercase_       )  # noqa: B010

       return cache_decorator_wrapper

     return cache_decorator_inner


if __name__ == "__main__":
       import doctest

       doctest.testmod()



def 			UpperCAmelCase__				(			_A      : dict							):





  '''simple docstring'''







  a__  =set()
  # To detect a back edge, keep track of vertices currently in the recursion stack
  a__  =set()
  return any(
      node not in visited and depth_first_search(_A	,      _A	,      _A	,      _A							)
      for node in graph							)




def 			UpperCAmelCase__				(			_A      : dict	,      _A      : int	,      _A      : set	,      _A      : set							):





  '''simple docstring'''







  visited.add(_A							)
  rec_stk.add(_A							)

  for node in graph[vertex]:
    if node not in visited:
      if depth_first_search(_A	,      _A	,      _A	,      _A							):
        return True
    elif node in rec_stk:
      return True

    # The node needs to be removed from recursion stack before function ends
  rec_stk.remove(_A							)
  return False


if __name__ == "__main__":
       from doctest import testmod

       testmod()
