





from __future__ import annotations

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

UpperCAmelCase_ 							=       TypeVar("""T""")
class      UpperCamelCase_						(					Generic[T]   ):
					lowerCAmelCase_							=		42  # Cache store of keys
					lowerCAmelCase_							=		42  # References of the keys in cache
					lowerCAmelCase_							=		10  # Maximum capacity of cache




					def __init__(						self			,  lowerCAmelCase_					)						->							None:
										_snake_case													=			deque()
										_snake_case													=			set()
										if not n:
															_snake_case													=			sys.maxsize
										elif n < 0:
															raise ValueError('n should be an integer greater than 0.'					)
										else:
															_snake_case													=			n




					def 		lowerCAmelCase     (						self			,  lowerCAmelCase_					)						->							None:
										if x not in self.key_reference:
															if len(self.dq_store					) == LRUCache._MAX_CAPACITY:
																				_snake_case													=			self.dq_store.pop()
																				self.key_reference.remove(lowerCAmelCase_					)
										else:
															self.dq_store.remove(lowerCAmelCase_					)

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




					def 		lowerCAmelCase     (						self					)						->							None:
										for k in self.dq_store:
															print(lowerCAmelCase_					)






					def __repr__(						self					)						->							str:
										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]"










def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    int    ,      UpperCamelCase__     :    int    ,      UpperCamelCase__     :    list[int]  )     ->	bool:



					'''simple docstring'''




					if graph[path[curr_ind - 1]][next_ver] == 0:
										return False

					# 2. Validate that next vertex is not already in path
					return not any(vertex == next_ver for vertex in path  )





def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    list[int]    ,      UpperCamelCase__     :    int  )     ->	bool:



					'''simple docstring'''




					if curr_ind == len(UpperCamelCase__  ):
										# return whether path exists between current and starting vertices
										return graph[path[curr_ind - 1]][path[0]] == 1

					# Recursive Step
					for next_ver in range(0    ,      len(UpperCamelCase__  )  ):
										if valid_connection(UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__    ,      UpperCamelCase__  ):
															# Insert current vertex  into path as next transition
															_snake_case													=			next_ver
															# Validate created path
															if util_hamilton_cycle(UpperCamelCase__    ,      UpperCamelCase__    ,      curr_ind + 1  ):
																				return True
															# Backtrack
															_snake_case													=			-1
					return False





def   lowerCamelCase__       (       UpperCamelCase__     :    list[list[int]]    ,      UpperCamelCase__     :    int = 0  )     ->	list[int]:



					'''simple docstring'''




					_snake_case													=			[-1] * (len(UpperCamelCase__  ) + 1)
					# initialize start and end of path with starting index
					_snake_case													=			_snake_case													=			start_index
					# evaluate and if we find answer return path either return empty array
					return path if util_hamilton_cycle(UpperCamelCase__    ,      UpperCamelCase__    ,      1  ) else []



