





from __future__ import annotations

import sys
from collections import deque
from typing import Generic, TypeVar

_UpperCAmelCase             =							TypeVar('T')






class        snake_case_    (		Generic[T]						):
  A_      							=   42  # Cache store of keys
  A_      							=   42  # References of the keys in cache
  A_      							=   10  # Maximum capacity of cache






  def __init__(							self			:					Tuple       ,  _snake_case			:					int      )->None:






   '''simple docstring'''

   __lowerCAmelCase					:	Tuple      =       deque()
   __lowerCAmelCase					:	Union[str, Any]      =       set()
   if not n:
    __lowerCAmelCase					:	Optional[int]      =       sys.maxsize
   elif n < 0:
    raise ValueError("""n should be an integer greater than 0."""      )
   else:
    __lowerCAmelCase					:	Any      =       n






  def 				UpperCAmelCase__						(							self			:					int       ,  _snake_case			:					T      )->None:






   '''simple docstring'''

   if x not in self.key_reference:
    if len(self.dq_store      ) == LRUCache._MAX_CAPACITY:
     __lowerCAmelCase					:	int      =       self.dq_store.pop()
     self.key_reference.remove(_snake_case      )
   else:
    self.dq_store.remove(_snake_case      )

   self.dq_store.appendleft(_snake_case      )
   self.key_reference.add(_snake_case      )






  def 				UpperCAmelCase__						(							self			:					Optional[Any]      )->None:






   '''simple docstring'''

   for k in self.dq_store:
    print(_snake_case      )






  def __repr__(							self			:					List[Any]      )->str:






   '''simple docstring'''

   return F'''LRUCache({self._MAX_CAPACITY}) => {list(self.dq_store      )}'''


if __name__ == "__main__":
      import doctest

      doctest.testmod()

      _UpperCAmelCase             =							LRUCache(4)
      lru_cache.refer('A')
      lru_cache.refer(2)
      lru_cache.refer(3)
      lru_cache.refer('A')
      lru_cache.refer(4)
      lru_cache.refer(5)
      lru_cache.display()

      print(lru_cache)
      assert str(lru_cache) == "LRUCache(4) => [5, 4, 'A', 3]"






_UpperCAmelCase             =							{0: [2, 3], 1: [0], 2: [1], 3: [4], 4: []}

_UpperCAmelCase             =							{0: [1, 2, 3], 1: [2], 2: [0], 3: [4], 4: [5], 5: [3]}






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:dict[int, list[int]]   ,   SCREAMING_SNAKE_CASE		:int   ,   SCREAMING_SNAKE_CASE		:list[bool]   )      ->   list[int]:
 __lowerCAmelCase					:	str      =       True
 __lowerCAmelCase					:	str      =       []

 for neighbour in graph[vert]:
  if not visited[neighbour]:
   order += topology_sort(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )

 order.append(SCREAMING_SNAKE_CASE   )

 return order






def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:dict[int, list[int]]   ,   SCREAMING_SNAKE_CASE		:int   ,   SCREAMING_SNAKE_CASE		:list[bool]   )      ->   list[int]:
 __lowerCAmelCase					:	Optional[Any]      =       True
 __lowerCAmelCase					:	Union[str, Any]      =       [vert]

 for neighbour in reversed_graph[vert]:
  if not visited[neighbour]:
   component += find_components(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )

 return component







def 	_SCREAMING_SNAKE_CASE		(      SCREAMING_SNAKE_CASE		:dict[int, list[int]]   )      ->   list[list[int]]:
 __lowerCAmelCase					:	Optional[Any]      =       len(SCREAMING_SNAKE_CASE   ) * [False]
 __lowerCAmelCase					:	dict[int, list[int]]      =       {vert: [] for vert in range(len(SCREAMING_SNAKE_CASE   )   )}

 for vert, neighbours in graph.items():
  for neighbour in neighbours:
   reversed_graph[neighbour].append(SCREAMING_SNAKE_CASE   )

 __lowerCAmelCase					:	Tuple      =       []
 for i, was_visited in enumerate(SCREAMING_SNAKE_CASE   ):
  if not was_visited:
   order += topology_sort(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )

 __lowerCAmelCase					:	Optional[Any]      =       []
 __lowerCAmelCase					:	Any      =       len(SCREAMING_SNAKE_CASE   ) * [False]

 for i in range(len(SCREAMING_SNAKE_CASE   )   ):
  __lowerCAmelCase					:	Optional[int]      =       order[len(SCREAMING_SNAKE_CASE   ) - i - 1]
  if not visited[vert]:
   __lowerCAmelCase					:	Any      =       find_components(SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   ,   SCREAMING_SNAKE_CASE   )
   components_list.append(SCREAMING_SNAKE_CASE   )

 return components_list