


from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

lowerCAmelCase__  :Dict             =							TypeVar('''T''')

def 	lowerCAmelCase__			(      a__:		int	)  ->		int:


							'''simple docstring'''





							return (position - 1) // 2

def 	lowerCAmelCase__			(      a__:		int	)  ->		int:


							'''simple docstring'''





							return (2 * position) + 1

def 	lowerCAmelCase__			(      a__:		int	)  ->		int:


							'''simple docstring'''





							return (2 * position) + 2

class 		__a				(    Generic[T]      ):
		def __init__(      self						)			->	None:




									"""simple docstring"""





									_UpperCAmelCase					=      []
									_UpperCAmelCase					=      {}
									_UpperCAmelCase					=      0
		def __len__(      self						)			->	int:




									"""simple docstring"""





									return self.elements
		def __repr__(      self						)			->	str:




									"""simple docstring"""





									return str(self.heap						)
		def      UpperCAmelCase__    (      self						)			->	bool:




									"""simple docstring"""





									return self.elements == 0
		def      UpperCAmelCase__    (      self      ,   _SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)			->	None:




									"""simple docstring"""





									self.heap.append((elem, weight)						)
									_UpperCAmelCase					=      self.elements
									self.elements += 1
									self._bubble_up(_SCREAMING_SNAKE_CASE						)
		def      UpperCAmelCase__    (      self						)			->	T:




									"""simple docstring"""





									if self.elements > 1:
																self._swap_nodes(0      ,   self.elements - 1						)
									_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap.pop()
									del self.position_map[elem]
									self.elements -= 1
									if self.elements > 0:
																_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[0]
																self._bubble_down(_SCREAMING_SNAKE_CASE						)
									return elem
		def      UpperCAmelCase__    (      self      ,   _SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)			->	None:




									"""simple docstring"""





									_UpperCAmelCase					=      self.position_map[elem]
									_UpperCAmelCase					=      (elem, weight)
									if position > 0:
																_UpperCAmelCase					=      get_parent_position(_SCREAMING_SNAKE_CASE						)
																_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[parent_position]
																if parent_weight > weight:
																							self._bubble_up(_SCREAMING_SNAKE_CASE						)
																else:
																							self._bubble_down(_SCREAMING_SNAKE_CASE						)
									else:
																self._bubble_down(_SCREAMING_SNAKE_CASE						)
		def      UpperCAmelCase__    (      self      ,   _SCREAMING_SNAKE_CASE						)			->	None:




									"""simple docstring"""





									_UpperCAmelCase					=      self.position_map[elem]
									if curr_pos == 0:
																return None
									_UpperCAmelCase					=      get_parent_position(_SCREAMING_SNAKE_CASE						)
									_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[curr_pos]
									_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[parent_position]
									if parent_weight > weight:
																self._swap_nodes(_SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)
																return self._bubble_up(_SCREAMING_SNAKE_CASE						)
									return None
		def      UpperCAmelCase__    (      self      ,   _SCREAMING_SNAKE_CASE						)			->	None:




									"""simple docstring"""





									_UpperCAmelCase					=      self.position_map[elem]
									_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[curr_pos]
									_UpperCAmelCase					=      get_child_left_position(_SCREAMING_SNAKE_CASE						)
									_UpperCAmelCase					=      get_child_right_position(_SCREAMING_SNAKE_CASE						)
									if child_left_position < self.elements and child_right_position < self.elements:
																_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[child_left_position]
																_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[child_right_position]
																if child_right_weight < child_left_weight and child_right_weight < weight:
																							self._swap_nodes(_SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)
																							return self._bubble_down(_SCREAMING_SNAKE_CASE						)
									if child_left_position < self.elements:
																_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[child_left_position]
																if child_left_weight < weight:
																							self._swap_nodes(_SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)
																							return self._bubble_down(_SCREAMING_SNAKE_CASE						)
									else:
																return None
									if child_right_position < self.elements:
																_UpperCAmelCase		,	_UpperCAmelCase					=      self.heap[child_right_position]
																if child_right_weight < weight:
																							self._swap_nodes(_SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)
																							return self._bubble_down(_SCREAMING_SNAKE_CASE						)
									return None






		def      UpperCAmelCase__    (      self      ,   _SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)			->	None:




									"""simple docstring"""





									_UpperCAmelCase					=      self.heap[nodea_pos][0]
									_UpperCAmelCase					=      self.heap[nodea_pos][0]
									_UpperCAmelCase		,	_UpperCAmelCase					=      (
									    self.heap[nodea_pos],
									    self.heap[nodea_pos],
									)
									_UpperCAmelCase					=      nodea_pos
									_UpperCAmelCase					=      nodea_pos



class 		__a				(    Generic[T]      ):
		def __init__(      self						)			->	None:




									"""simple docstring"""





									_UpperCAmelCase					=      {}
									_UpperCAmelCase					=      0
		def __repr__(      self						)			->	str:




									"""simple docstring"""





									return str(self.connections						)
		def __len__(      self						)			->	int:




									"""simple docstring"""





									return self.nodes
		def      UpperCAmelCase__    (      self      ,   _SCREAMING_SNAKE_CASE						)			->	None:




									"""simple docstring"""





									if node not in self.connections:
																_UpperCAmelCase					=      {}
																self.nodes += 1






		def      UpperCAmelCase__    (      self      ,   _SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE      ,   _SCREAMING_SNAKE_CASE						)			->	None:




									"""simple docstring"""





									self.add_node(_SCREAMING_SNAKE_CASE						)
									self.add_node(_SCREAMING_SNAKE_CASE						)
									_UpperCAmelCase					=      weight
									_UpperCAmelCase					=      weight



def 	lowerCAmelCase__			(      a__:		GraphUndirectedWeighted[T]      ,  )  ->		tuple[dict[T, int], dict[T, T | None]]:


							'''simple docstring'''





							_UpperCAmelCase					=      {node: maxsize for node in graph.connections}
							_UpperCAmelCase					=      {node: None for node in graph.connections}

							_UpperCAmelCase					=      MinPriorityQueue()
							for node, weight in dist.items():
														priority_queue.push(a__      ,  a__	)

							if priority_queue.is_empty():
														return dist, parent

							# initialization
							_UpperCAmelCase					=      priority_queue.extract_min()
							_UpperCAmelCase					=      0
							for neighbour in graph.connections[node]:
														if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
																					_UpperCAmelCase					=      dist[node] + graph.connections[node][neighbour]
																					priority_queue.update_key(a__      ,  dist[neighbour]	)
																					_UpperCAmelCase					=      node

    # running prim's algorithm
							while not priority_queue.is_empty():
														_UpperCAmelCase					=      priority_queue.extract_min()
														for neighbour in graph.connections[node]:
																					if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
																												_UpperCAmelCase					=      dist[node] + graph.connections[node][neighbour]
																												priority_queue.update_key(a__      ,  dist[neighbour]	)
																												_UpperCAmelCase					=      node
							return dist, parent




from __future__ import annotations

import numpy as np
from numpy import floataa
from numpy.typing import NDArray

def 	lowerCAmelCase__			(      a__:		NDArray[floataa]      ,  a__:		NDArray[floataa]      ,  a__:		list[int]      ,  a__:		int      ,  )  ->		list[float]:


							'''simple docstring'''





							_UpperCAmelCase		,	_UpperCAmelCase					=      coefficient_matrix.shape
							_UpperCAmelCase		,	_UpperCAmelCase					=      constant_matrix.shape

							if rowsa != colsa:
														_UpperCAmelCase					=      F'''Coefficient matrix dimensions must be nxn but received {rowsa}x{colsa}'''
														raise ValueError(a__	)

							if colsa != 1:
														_UpperCAmelCase					=      F'''Constant matrix must be nx1 but received {rowsa}x{colsa}'''
														raise ValueError(a__	)

							if rowsa != rowsa:
														_UpperCAmelCase					=      (
														    'Coefficient and constant matrices dimensions must be nxn and nx1 but '
														    F'''received {rowsa}x{colsa} and {rowsa}x{colsa}'''
														)
														raise ValueError(a__	)

							if len(a__	) != rowsa:
														_UpperCAmelCase					=      (
														    'Number of initial values must be equal to number of rows in coefficient '
														    F'''matrix but received {len(a__	)} and {rowsa}'''
														)
														raise ValueError(a__	)

							if iterations <= 0:
														raise ValueError('Iterations must be at least 1'	)

							_UpperCAmelCase					=      np.concatenate(
							    (coefficient_matrix, constant_matrix)      ,  axis=1	)

							_UpperCAmelCase		,	_UpperCAmelCase					=      table.shape

							strictly_diagonally_dominant(a__	)

							# Iterates the whole matrix for given number of times
							for _ in range(a__	):
														_UpperCAmelCase					=      []
														for row in range(a__	):
																					_UpperCAmelCase					=      0
																					for col in range(a__	):
																												if col == row:
																																			_UpperCAmelCase					=      table[row][col]
																												elif col == cols - 1:
																																			_UpperCAmelCase					=      table[row][col]
																												else:
																																			temp += (-1) * table[row][col] * init_val[col]
																					_UpperCAmelCase					=      (temp + val) / denom
																					new_val.append(a__	)
														_UpperCAmelCase					=      new_val

							return [float(a__	) for i in new_val]

def 	lowerCAmelCase__			(      a__:		NDArray[floataa]	)  ->		bool:


							'''simple docstring'''





							_UpperCAmelCase		,	_UpperCAmelCase					=      table.shape

							_UpperCAmelCase					=      True

							for i in range(0      ,  a__	):
														_UpperCAmelCase					=      0
														for j in range(0      ,  cols - 1	):
																					if i == j:
																												continue
																					else:
																												total += table[i][j]

														if table[i][i] <= total:
																					raise ValueError('Coefficient matrix is not strictly diagonally dominant'	)

							return is_diagonally_dominant


# Test Cases
if __name__ == "__main__":
		import doctest

		doctest.testmod()
