





'''simple docstring'''






from __future__ import annotations

A   : List[str]             =			{
    'A': ['B', 'C', 'E'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['A', 'B', 'D'],
    'F': ['C'],
    'G': ['C'],
}







class 			lowerCamelCase					:


					def __init__(					self	:  Optional[int]       ,     __snake_case	:  dict[str, list[str]]       ,     __snake_case	:  str       ):





											'''simple docstring'''





											_snake_case:   str  					=		graph
											# mapping node to its parent in resulting breadth first tree
											_snake_case:   dict[str, str | None]  					=		{}
											_snake_case:   List[str]  					=		source_vertex


					def    SCREAMING_SNAKE_CASE_		(					self	:  List[str]       ):





											'''simple docstring'''





											_snake_case:   Optional[int]  					=		{self.source_vertex}
											_snake_case:   List[Any]  					=		None
											_snake_case:   Any  					=		[self.source_vertex]  # first in first out queue

											while queue:
																	_snake_case:   int  					=		queue.pop(0       )
																	for adjacent_vertex in self.graph[vertex]:
																							if adjacent_vertex not in visited:
																													visited.add(__snake_case       )
																													_snake_case:   List[str]  					=		vertex
																													queue.append(__snake_case       )




					def    SCREAMING_SNAKE_CASE_		(					self	:  List[Any]       ,     __snake_case	:  str       ):





											'''simple docstring'''





											if target_vertex == self.source_vertex:
																	return self.source_vertex

											_snake_case:   Optional[Any]  					=		self.parent.get(__snake_case       )
											if target_vertex_parent is None:
																	_snake_case:   List[str]  					=		(
																	    f'''No path from vertex: {self.source_vertex} to vertex: {target_vertex}'''
																	)
																	raise ValueError(__snake_case       )

											return self.shortest_path(__snake_case       ) + f'''->{target_vertex}'''


if __name__ == "__main__":
		A   : Any             =			Graph(graph, 'G')
		g.breath_first_search()
		print(g.shortest_path('D'))
		print(g.shortest_path('G'))
		print(g.shortest_path('Foo'))












'''simple docstring'''






from __future__ import annotations

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

A   : str             =			TypeVar('T')







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


					def __init__(					self	:  List[Any]       ,     __snake_case	:  int       ):





											'''simple docstring'''





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


					def    SCREAMING_SNAKE_CASE_		(					self	:  Any       ,     __snake_case	:  T       ):





											'''simple docstring'''





											if x not in self.key_reference:
																	if len(self.dq_store       ) == LRUCache._MAX_CAPACITY:
																							_snake_case:   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    SCREAMING_SNAKE_CASE_		(					self	:  int       ):





											'''simple docstring'''





											for k in self.dq_store:
																	print(__snake_case       )




					def __repr__(					self	:  List[Any]       ):





											'''simple docstring'''





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


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		A   : LRUCache[str | int]             =			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]"





