


'''simple docstring'''


from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

UpperCAmelCase_						:  Dict				  =						TypeVar('T')







def      snake_case_  (    SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				return (position - 1) // 2







def      snake_case_  (    SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				return (2 * position) + 1







def      snake_case_  (    SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				return (2 * position) + 2





class        lowercase__    (		Generic[T]   ):





							'''simple docstring'''


							def __init__(       self    ):
											_SCREAMING_SNAKE_CASE					:			list[tuple[T, int]]							= []
											_SCREAMING_SNAKE_CASE					:			dict[T, int]							= {}
											_SCREAMING_SNAKE_CASE					:			int							= 0






							def __len__(       self    ):
											return self.elements






							def __repr__(       self    ):
											return str(self.heap    )






							def UpperCAmelCase_      (       self    ):
											# Check if the priority queue is empty
											return self.elements == 0






							def UpperCAmelCase_      (       self       ,   __snake_case       ,   __snake_case    ):
											# Add an element with given priority to the queue
											self.heap.append((elem, weight)    )
											_SCREAMING_SNAKE_CASE					:			str							= self.elements
											self.elements += 1
											self._bubble_up(__snake_case    )






							def UpperCAmelCase_      (       self    ):
											# Remove and return the element with lowest weight (highest priority)
											if self.elements > 1:
															self._swap_nodes(0       ,   self.elements - 1    )
											_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			int							= self.heap.pop()
											del self.position_map[elem]
											self.elements -= 1
											if self.elements > 0:
															_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			Optional[Any]							= self.heap[0]
															self._bubble_down(__snake_case    )
											return elem






							def UpperCAmelCase_      (       self       ,   __snake_case       ,   __snake_case    ):
											# Update the weight of the given key
											_SCREAMING_SNAKE_CASE					:			List[str]							= self.position_map[elem]
											_SCREAMING_SNAKE_CASE					:			Tuple							= (elem, weight)
											if position > 0:
															_SCREAMING_SNAKE_CASE					:			Tuple							= get_parent_position(__snake_case    )
															_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			int							= self.heap[parent_position]
															if parent_weight > weight:
																			self._bubble_up(__snake_case    )
															else:
																			self._bubble_down(__snake_case    )
											else:
															self._bubble_down(__snake_case    )






							def UpperCAmelCase_      (       self       ,   __snake_case    ):
											# Place a node at the proper position (upward movement) [to be used internally
											# only]
											_SCREAMING_SNAKE_CASE					:			Any							= self.position_map[elem]
											if curr_pos == 0:
															return None
											_SCREAMING_SNAKE_CASE					:			str							= get_parent_position(__snake_case    )
											_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			int							= self.heap[curr_pos]
											_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			int							= self.heap[parent_position]
											if parent_weight > weight:
															self._swap_nodes(__snake_case       ,   __snake_case    )
															return self._bubble_up(__snake_case    )
											return None






							def UpperCAmelCase_      (       self       ,   __snake_case    ):
											# Place a node at the proper position (downward movement) [to be used
											# internally only]
											_SCREAMING_SNAKE_CASE					:			str							= self.position_map[elem]
											_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			Any							= self.heap[curr_pos]
											_SCREAMING_SNAKE_CASE					:			List[str]							= get_child_left_position(__snake_case    )
											_SCREAMING_SNAKE_CASE					:			str							= get_child_right_position(__snake_case    )
											if child_left_position < self.elements and child_right_position < self.elements:
															_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			str							= self.heap[child_left_position]
															_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			Tuple							= self.heap[child_right_position]
															if child_right_weight < child_left_weight and child_right_weight < weight:
																			self._swap_nodes(__snake_case       ,   __snake_case    )
																			return self._bubble_down(__snake_case    )
											if child_left_position < self.elements:
															_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			int							= self.heap[child_left_position]
															if child_left_weight < weight:
																			self._swap_nodes(__snake_case       ,   __snake_case    )
																			return self._bubble_down(__snake_case    )
											else:
															return None
											if child_right_position < self.elements:
															_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			Any							= self.heap[child_right_position]
															if child_right_weight < weight:
																			self._swap_nodes(__snake_case       ,   __snake_case    )
																			return self._bubble_down(__snake_case    )
											return None






							def UpperCAmelCase_      (       self       ,   __snake_case       ,   __snake_case    ):
											# Swap the nodes at the given positions
											_SCREAMING_SNAKE_CASE					:			Tuple							= self.heap[nodea_pos][0]
											_SCREAMING_SNAKE_CASE					:			Optional[int]							= self.heap[nodea_pos][0]
											_SCREAMING_SNAKE_CASE						,			_SCREAMING_SNAKE_CASE					:			Dict							= (
											    self.heap[nodea_pos],
											    self.heap[nodea_pos],
											)
											_SCREAMING_SNAKE_CASE					:			Any							= nodea_pos
											_SCREAMING_SNAKE_CASE					:			int							= nodea_pos





class        lowercase__    (		Generic[T]   ):





							'''simple docstring'''


							def __init__(       self    ):
											_SCREAMING_SNAKE_CASE					:			dict[T, dict[T, int]]							= {}
											_SCREAMING_SNAKE_CASE					:			int							= 0






							def __repr__(       self    ):
											return str(self.connections    )






							def __len__(       self    ):
											return self.nodes






							def UpperCAmelCase_      (       self       ,   __snake_case    ):
											# Add a node in the graph if it is not in the graph
											if node not in self.connections:
															_SCREAMING_SNAKE_CASE					:			Any							= {}
															self.nodes += 1






							def UpperCAmelCase_      (       self       ,   __snake_case       ,   __snake_case       ,   __snake_case    ):
											# Add an edge between 2 nodes in the graph
											self.add_node(__snake_case    )
											self.add_node(__snake_case    )
											_SCREAMING_SNAKE_CASE					:			List[Any]							= weight
											_SCREAMING_SNAKE_CASE					:			List[str]							= weight







def      snake_case_  (    SCREAMING_SNAKE_CASE__				, ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			dict[T, int]							= {node: maxsize for node in graph.connections}
				_SCREAMING_SNAKE_CASE					:			dict[T, T | None]							= {node: None for node in graph.connections}

				_SCREAMING_SNAKE_CASE					:			MinPriorityQueue[T]							= MinPriorityQueue()
				for node, weight in dist.items():
								priority_queue.push(SCREAMING_SNAKE_CASE__				, SCREAMING_SNAKE_CASE__	)

				if priority_queue.is_empty():
								return dist, parent

				# initialization
				_SCREAMING_SNAKE_CASE					:			Union[str, Any]							= priority_queue.extract_min()
				_SCREAMING_SNAKE_CASE					:			int							= 0
				for neighbour in graph.connections[node]:
								if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
												_SCREAMING_SNAKE_CASE					:			str							= dist[node] + graph.connections[node][neighbour]
												priority_queue.update_key(SCREAMING_SNAKE_CASE__				, dist[neighbour]	)
												_SCREAMING_SNAKE_CASE					:			str							= node

    # running prim's algorithm
				while not priority_queue.is_empty():
								_SCREAMING_SNAKE_CASE					:			Optional[int]							= priority_queue.extract_min()
								for neighbour in graph.connections[node]:
												if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
																_SCREAMING_SNAKE_CASE					:			Union[str, Any]							= dist[node] + graph.connections[node][neighbour]
																priority_queue.update_key(SCREAMING_SNAKE_CASE__				, dist[neighbour]	)
																_SCREAMING_SNAKE_CASE					:			List[Any]							= node
				return dist, parent








'''simple docstring'''


import math







def      snake_case_  (    SCREAMING_SNAKE_CASE__	):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			Tuple							= math.loga(math.sqrt(4 * positive_integer + 1	) / 2 + 1 / 2	)

				return exponent == int(SCREAMING_SNAKE_CASE__	)







def      snake_case_  (    SCREAMING_SNAKE_CASE__ = 1 / 1_2345	):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE					:			str							= 0
				_SCREAMING_SNAKE_CASE					:			str							= 0

				_SCREAMING_SNAKE_CASE					:			int							= 3
				while True:
								_SCREAMING_SNAKE_CASE					:			Optional[int]							= (integer**2 - 1) / 4
								# if candidate is an integer, then there is a partition for k
								if partition_candidate == int(SCREAMING_SNAKE_CASE__	):
												_SCREAMING_SNAKE_CASE					:			int							= int(SCREAMING_SNAKE_CASE__	)
												total_partitions += 1
												if check_partition_perfect(SCREAMING_SNAKE_CASE__	):
																perfect_partitions += 1
								if perfect_partitions > 0:
												if perfect_partitions / total_partitions < max_proportion:
																return int(SCREAMING_SNAKE_CASE__	)
								integer += 1


if __name__ == "__main__":
				print(F"{solution() = }")




