

from __future__ import annotations

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

a_         =      TypeVar('T')
a_         =      TypeVar('U')






class _UpperCamelCase							(							Generic[T, U]				):
			'''simple docstring'''







			def __init__(     self							:	Tuple , a							:	T | None , a							:	U | None		)							->    Optional[int]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Optional[int]			       =    key
				SCREAMING_SNAKE_CASE				: str			       =    val
				SCREAMING_SNAKE_CASE				: int			       =    0
				SCREAMING_SNAKE_CASE				: DoubleLinkedListNode[T, U] | None			       =    None
				SCREAMING_SNAKE_CASE				: DoubleLinkedListNode[T, U] | None			       =    None






			def __repr__(     self							:	Any		)							->    str:

				"""simple docstring"""

				return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
				    self.key , self.val , self.freq , self.next is not None , self.prev is not None		)






class _UpperCamelCase							(							Generic[T, U]				):
			'''simple docstring'''







			def __init__(     self							:	List[Any]		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: DoubleLinkedListNode[T, U]			       =    DoubleLinkedListNode(a , a		)
				SCREAMING_SNAKE_CASE				: DoubleLinkedListNode[T, U]			       =    DoubleLinkedListNode(a , a		)
				SCREAMING_SNAKE_CASE       ,SCREAMING_SNAKE_CASE				: List[Any]			       =    self.rear, self.head
			def __repr__(     self							:	str		)							->    str:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Dict			       =    ["DoubleLinkedList"]
				SCREAMING_SNAKE_CASE				: Any			       =    self.head
				while node.next is not None:
					rep.append(str(a		)		)
					SCREAMING_SNAKE_CASE				: Any			       =    node.next
				rep.append(str(self.rear		)		)
				return ",\n    ".join(a		)
			def 							__UpperCamelCase	(     self							:	Tuple , a							:	DoubleLinkedListNode[T, U]		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Optional[Any]			       =    self.rear.prev

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

				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    node
				SCREAMING_SNAKE_CASE				: Optional[int]			       =    previous
				SCREAMING_SNAKE_CASE				: Tuple			       =    node
				SCREAMING_SNAKE_CASE				: int			       =    self.rear
				node.freq += 1
				self._position_node(a		)
			def 							__UpperCamelCase	(     self							:	List[str] , a							:	DoubleLinkedListNode[T, U]		)							->    None:

				"""simple docstring"""

				while node.prev is not None and node.prev.freq > node.freq:
					# swap node with previous node
					SCREAMING_SNAKE_CASE				: Tuple			       =    node.prev

					SCREAMING_SNAKE_CASE				: int			       =    previous_node.prev
					SCREAMING_SNAKE_CASE				: Any			       =    node.prev
					SCREAMING_SNAKE_CASE				: str			       =    previous_node
					SCREAMING_SNAKE_CASE				: Optional[int]			       =    node






			def 							__UpperCamelCase	(     self							:	Any , a							:	DoubleLinkedListNode[T, U]		)							->    DoubleLinkedListNode[T, U] | None:

				"""simple docstring"""

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

				SCREAMING_SNAKE_CASE				: str			       =    node.next
				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    node.prev
				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    None
				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    None
				return node






class _UpperCamelCase							(							Generic[T, U]				):
			'''simple docstring'''







			lowerCamelCase__          ={}
			def __init__(     self							:	Dict , a							:	int		)							->    Optional[Any]:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: DoubleLinkedList[T, U]			       =    DoubleLinkedList()
				SCREAMING_SNAKE_CASE				: Optional[Any]			       =    capacity
				SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    0
				SCREAMING_SNAKE_CASE				: Dict			       =    0
				SCREAMING_SNAKE_CASE				: List[Any]			       =    0
				SCREAMING_SNAKE_CASE				: dict[T, DoubleLinkedListNode[T, U]]			       =    {}
			def __repr__(     self							:	Dict		)							->    str:

				"""simple docstring"""

				return (
				    F"CacheInfo(hits={self.hits}, misses={self.miss}, "
				    F"capacity={self.capacity}, current_size={self.num_keys})"
				)
			def __contains__(     self							:	Tuple , a							:	T		)							->    bool:

				"""simple docstring"""

				return key in self.cache
			def 							__UpperCamelCase	(     self							:	str , a							:	T		)							->    U | None:

				"""simple docstring"""

				if key in self.cache:
					self.hits += 1
					SCREAMING_SNAKE_CASE				: DoubleLinkedListNode[T, U]			       =    self.cache[key]
					SCREAMING_SNAKE_CASE				: List[str]			       =    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(a		)
					return node.val
				self.miss += 1
				return None
			def 							__UpperCamelCase	(     self							:	Union[str, Any] , a							:	T , a							:	U		)							->    None:

				"""simple docstring"""

				if key not in self.cache:
					if self.num_keys >= self.capacity:
						# delete first node when over capacity
						SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    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(a		) is not None
						# first_node guaranteed to be in list

						del self.cache[first_node.key]
						self.num_keys -= 1
					SCREAMING_SNAKE_CASE				: Optional[int]			       =    DoubleLinkedListNode(a , a		)
					self.list.add(self.cache[key]		)
					self.num_keys += 1

				else:
					SCREAMING_SNAKE_CASE				: List[Any]			       =    self.list.remove(self.cache[key]		)
					assert node is not None  # node guaranteed to be in list
					SCREAMING_SNAKE_CASE				: Optional[int]			       =    value
					self.list.add(a		)






			@classmethod
			def 							__UpperCamelCase	(     cls							:	type[LFUCache[T, U]] , a							:	int = 128		)							->    Callable[[Callable[[T], U]], Callable[..., U]]:

				"""simple docstring"""

				def cache_decorator_inner(a							:	Callable[[T], U]		) -> Callable[..., U]:
					def cache_decorator_wrapper(*a							:	T		) -> U:
						if func not in cls.decorator_function_to_instance_map:
							SCREAMING_SNAKE_CASE				: Optional[int]			       =    LFUCache(a		)

						SCREAMING_SNAKE_CASE				: List[Any]			       =    cls.decorator_function_to_instance_map[func].get(args[0]		)
						if result is None:
							SCREAMING_SNAKE_CASE				: List[str]			       =    func(*a		)
							cls.decorator_function_to_instance_map[func].put(args[0] , a		)
						return result

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

					setattr(a , "cache_info" , a		)  # noqa: B010

					return cache_decorator_wrapper

				return cache_decorator_inner


if __name__ == "__main__":
			import doctest

			doctest.testmod()


from __future__ import annotations






class _UpperCamelCase							:
			'''simple docstring'''







			def __init__(     self							:	List[Any] , a							:	int		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[str]			       =    vertices
				SCREAMING_SNAKE_CASE				: Tuple			       =    [[0] * vertices for _ in range(a		)]
			def 							__UpperCamelCase	(     self							:	Dict , a							:	list[int]		)							->    None:

				"""simple docstring"""

				print("Vertex \t Distance from Source"		)
				for vertex in range(self.vertices		):
					print(a , "\t\t" , distances_from_source[vertex]		)
			def 							__UpperCamelCase	(     self							:	Tuple , a							:	list[int] , a							:	list[bool]		)							->    int:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: Dict			       =    1e7
				SCREAMING_SNAKE_CASE				: int			       =    0

				# Search not nearest vertex not in the shortest path tree
				for vertex in range(self.vertices		):
					if distances_from_source[vertex] < minimum and visited[vertex] is False:
						SCREAMING_SNAKE_CASE				: Optional[int]			       =    distances_from_source[vertex]
						SCREAMING_SNAKE_CASE				: Optional[Any]			       =    vertex
				return min_index






			def 							__UpperCamelCase	(     self							:	Any , a							:	int		)							->    None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE				: List[str]			       =    [int(1e7		)] * self.vertices  # distances from the source
				SCREAMING_SNAKE_CASE				: Tuple			       =    0
				SCREAMING_SNAKE_CASE				: List[Any]			       =    [False] * self.vertices

				for _ in range(self.vertices		):
					SCREAMING_SNAKE_CASE				: Union[str, Any]			       =    self.minimum_distance(a , a		)
					SCREAMING_SNAKE_CASE				: List[str]			       =    True

					# Update dist value of the adjacent vertices
					# of the picked vertex only if the current
					# distance is greater than new distance and
					# the vertex in not in the shortest path tree
					for v in range(self.vertices		):
						if (
						    self.graph[u][v] > 0
						    and visited[v] is False
						    and distances[v] > distances[u] + self.graph[u][v]
						):
							SCREAMING_SNAKE_CASE				: int			       =    distances[u] + self.graph[u][v]

				self.print_solution(a		)


if __name__ == "__main__":
			a_         =      Graph(9)
			a_         =      [
			    [0, 4, 0, 0, 0, 0, 0, 8, 0],
			    [4, 0, 8, 0, 0, 0, 0, 11, 0],
			    [0, 8, 0, 7, 0, 4, 0, 0, 2],
			    [0, 0, 7, 0, 9, 14, 0, 0, 0],
			    [0, 0, 0, 9, 0, 10, 0, 0, 0],
			    [0, 0, 4, 14, 10, 0, 2, 0, 0],
			    [0, 0, 0, 0, 0, 2, 0, 1, 6],
			    [8, 11, 0, 0, 0, 0, 1, 0, 7],
			    [0, 0, 2, 0, 0, 0, 6, 7, 0],
			]
			graph.dijkstra(0)