






"""simple docstring"""



from __future__ import annotations

import math
import random
from collections.abc import Collection
from typing import overload







class        lowercase__      :


			def __init__(				self					:  Optional[int]       ,	snake_case__					:  Collection[float] | None = None ):
										if components is None:
																	lowerCamelCase_	:							Optional[Any]									=[]
										lowerCamelCase_	:							Tuple									=list(snake_case__ )


			def __len__(				self					:  Union[str, Any] ):
										return len(self.__components )


			def __str__(				self					:  Any ):
										return "(" + ",".join(map(snake_case__       ,	self.__components ) ) + ")"


			def __add__(				self					:  Dict       ,	snake_case__					:  Vector ):
										lowerCamelCase_	:							List[Any]									=len(self )
										if size == len(snake_case__ ):
																	lowerCamelCase_	:							Tuple									=[self.__components[i] + other.component(snake_case__ ) for i in range(snake_case__ )]
																	return Vector(snake_case__ )
										else:
																	raise Exception("must have the same size" )


			def __sub__(				self					:  Tuple       ,	snake_case__					:  Vector ):
										lowerCamelCase_	:							Optional[Any]									=len(self )
										if size == len(snake_case__ ):
																	lowerCamelCase_	:							Dict									=[self.__components[i] - other.component(snake_case__ ) for i in range(snake_case__ )]
																	return Vector(snake_case__ )
										else:  # error case
																	raise Exception("must have the same size" )


			@overload
			def __mul__(				self					:  str       ,	snake_case__					:  float ):
										...


			@overload
			def __mul__(				self					:  Union[str, Any]       ,	snake_case__					:  Vector ):
										...


			def __mul__(				self					:  Any       ,	snake_case__					:  float | Vector ):
										if isinstance(snake_case__       ,	(float, int) ):
																	lowerCamelCase_	:							int									=[c * other for c in self.__components]
																	return Vector(snake_case__ )
										elif isinstance(snake_case__       ,	snake_case__ ) and len(self ) == len(snake_case__ ):
																	lowerCamelCase_	:							Optional[Any]									=len(self )
																	lowerCamelCase_	:							Union[str, Any]									=[self.__components[i] * other.component(snake_case__ ) for i in range(snake_case__ )]
																	return sum(snake_case__ )
										else:  # error case
																	raise Exception("invalid operand!" )


			def      UpperCAmelCase__						(				self					:  Any ):
										return Vector(self.__components )


			def      UpperCAmelCase__						(				self					:  Union[str, Any]       ,	snake_case__					:  int ):
										if isinstance(snake_case__       ,	snake_case__ ) and -len(self.__components ) <= i < len(self.__components ):
																	return self.__components[i]
										else:
																	raise Exception("index out of range" )


			def      UpperCAmelCase__						(				self					:  Union[str, Any]       ,	snake_case__					:  int       ,	snake_case__					:  float ):
										assert -len(self.__components ) <= pos < len(self.__components )
										lowerCamelCase_	:							Tuple									=value


			def      UpperCAmelCase__						(				self					:  Union[str, Any] ):
										if len(self.__components ) == 0:
																	raise Exception("Vector is empty" )
										lowerCamelCase_	:							str									=[c**2 for c in self.__components]
										return math.sqrt(sum(snake_case__ ) )


			def      UpperCAmelCase__						(				self					:  Any       ,	snake_case__					:  Vector       ,	snake_case__					:  bool = False ):
										lowerCamelCase_	:							Optional[Any]									=self * other
										lowerCamelCase_	:							Optional[int]									=self.euclidean_length() * other.euclidean_length()
										if deg:
																	return math.degrees(math.acos(num / den ) )
										else:
																	return math.acos(num / den )


def 			_snake_case    (					lowerCamelCase__     :   int  )    ->     Vector:
							assert isinstance(lowerCamelCase__    ,						lowerCamelCase__  )
							return Vector([0] * dimension  )

def 			_snake_case    (					lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int  )    ->     Vector:
							assert isinstance(lowerCamelCase__    ,						lowerCamelCase__  ) and (isinstance(lowerCamelCase__    ,						lowerCamelCase__  ))
							lowerCamelCase_	:							Union[str, Any]									=[0] * dimension
							lowerCamelCase_	:							int									=1
							return Vector(lowerCamelCase__  )

def 			_snake_case    (					lowerCamelCase__     :   float    ,						lowerCamelCase__     :   Vector    ,						lowerCamelCase__     :   Vector  )    ->     Vector:
							assert (
							    isinstance(lowerCamelCase__    ,						lowerCamelCase__  )
							    and isinstance(lowerCamelCase__    ,						lowerCamelCase__  )
							    and (isinstance(lowerCamelCase__    ,						(int, float)  ))
							)
							return x * scalar + y

def 			_snake_case    (					lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int  )    ->     Vector:
							random.seed(lowerCamelCase__  )
							lowerCamelCase_	:							Union[str, Any]									=[random.randint(lowerCamelCase__    ,						lowerCamelCase__  ) for _ in range(lowerCamelCase__  )]
							return Vector(lowerCamelCase__  )







class        lowercase__      :


			def __init__(				self					:  str       ,	snake_case__					:  list[list[float]]       ,	snake_case__					:  int       ,	snake_case__					:  int ):
										lowerCamelCase_	:							List[str]									=matrix
										lowerCamelCase_	:							Tuple									=w
										lowerCamelCase_	:							Optional[int]									=h


			def __str__(				self					:  List[str] ):
										lowerCamelCase_	:							int									=""
										for i in range(self.__height ):
																	ans += "|"
																	for j in range(self.__width ):
																								if j < self.__width - 1:
																															ans += str(self.__matrix[i][j] ) + ","
																								else:
																															ans += str(self.__matrix[i][j] ) + "|\n"
										return ans


			def __add__(				self					:  Optional[Any]       ,	snake_case__					:  Matrix ):
										if self.__width == other.width() and self.__height == other.height():
																	lowerCamelCase_	:							Optional[Any]									=[]
																	for i in range(self.__height ):
																								lowerCamelCase_	:							Dict									=[
																								    self.__matrix[i][j] + other.component(snake_case__       ,	snake_case__ )
																								    for j in range(self.__width )
																								]
																								matrix.append(snake_case__ )
																	return Matrix(snake_case__       ,	self.__width       ,	self.__height )
										else:
																	raise Exception("matrix must have the same dimension!" )


			def __sub__(				self					:  Tuple       ,	snake_case__					:  Matrix ):
										if self.__width == other.width() and self.__height == other.height():
																	lowerCamelCase_	:							List[str]									=[]
																	for i in range(self.__height ):
																								lowerCamelCase_	:							Dict									=[
																								    self.__matrix[i][j] - other.component(snake_case__       ,	snake_case__ )
																								    for j in range(self.__width )
																								]
																								matrix.append(snake_case__ )
																	return Matrix(snake_case__       ,	self.__width       ,	self.__height )
										else:
																	raise Exception("matrices must have the same dimension!" )


			@overload
			def __mul__(				self					:  Optional[Any]       ,	snake_case__					:  float ):
										...


			@overload
			def __mul__(				self					:  Union[str, Any]       ,	snake_case__					:  Vector ):
										...


			def __mul__(				self					:  Dict       ,	snake_case__					:  float | Vector ):
										if isinstance(snake_case__       ,	snake_case__ ):  # matrix-vector
																	if len(snake_case__ ) == self.__width:
																								lowerCamelCase_	:							List[Any]									=zero_vector(self.__height )
																								for i in range(self.__height ):
																															lowerCamelCase_	:							Any									=[
																															    self.__matrix[i][j] * other.component(snake_case__ )
																															    for j in range(self.__width )
																															]
																															ans.change_component(snake_case__       ,	sum(snake_case__ ) )
																								return ans
																	else:
																								raise Exception(
																								    "vector must have the same size as the "
																								    "number of columns of the matrix!" )
										elif isinstance(snake_case__       ,	(int, float) ):  # matrix-scalar
																	lowerCamelCase_	:							Optional[int]									=[
																	    [self.__matrix[i][j] * other for j in range(self.__width )]
																	    for i in range(self.__height )
																	]
																	return Matrix(snake_case__       ,	self.__width       ,	self.__height )
										return None


			def      UpperCAmelCase__						(				self					:  List[Any] ):
										return self.__height


			def      UpperCAmelCase__						(				self					:  Any ):
										return self.__width


			def      UpperCAmelCase__						(				self					:  Union[str, Any]       ,	snake_case__					:  int       ,	snake_case__					:  int ):
										if 0 <= x < self.__height and 0 <= y < self.__width:
																	return self.__matrix[x][y]
										else:
																	raise Exception("change_component: indices out of bounds" )


			def      UpperCAmelCase__						(				self					:  Dict       ,	snake_case__					:  int       ,	snake_case__					:  int       ,	snake_case__					:  float ):
										if 0 <= x < self.__height and 0 <= y < self.__width:
																	lowerCamelCase_	:							Union[str, Any]									=value
										else:
																	raise Exception("change_component: indices out of bounds" )


			def      UpperCAmelCase__						(				self					:  Union[str, Any]       ,	snake_case__					:  int       ,	snake_case__					:  int ):
										if self.__height != self.__width:
																	raise Exception("Matrix is not square" )
										lowerCamelCase_	:							Optional[int]									=self.__matrix[:x] + self.__matrix[x + 1 :]
										for i in range(len(snake_case__ ) ):
																	lowerCamelCase_	:							List[Any]									=minor[i][:y] + minor[i][y + 1 :]
										return Matrix(snake_case__       ,	self.__width - 1       ,	self.__height - 1 ).determinant()


			def      UpperCAmelCase__						(				self					:  Union[str, Any]       ,	snake_case__					:  int       ,	snake_case__					:  int ):
										if self.__height != self.__width:
																	raise Exception("Matrix is not square" )
										if 0 <= x < self.__height and 0 <= y < self.__width:
																	return (-1) ** (x + y) * self.minor(snake_case__       ,	snake_case__ )
										else:
																	raise Exception("Indices out of bounds" )


			def      UpperCAmelCase__						(				self					:  Optional[int] ):
										if self.__height != self.__width:
																	raise Exception("Matrix is not square" )
										if self.__height < 1:
																	raise Exception("Matrix has no element" )
										elif self.__height == 1:
																	return self.__matrix[0][0]
										elif self.__height == 2:
																	return (
																	    self.__matrix[0][0] * self.__matrix[1][1]
																	    - self.__matrix[0][1] * self.__matrix[1][0]
																	)
										else:
																	lowerCamelCase_	:							Union[str, Any]									=[
																	    self.__matrix[0][y] * self.cofactor(0       ,	snake_case__ ) for y in range(self.__width )
																	]
																	return sum(snake_case__ )


def 			_snake_case    (					lowerCamelCase__     :   int  )    ->     Matrix:
							lowerCamelCase_	:							list[list[float]]									=[[0] * n for _ in range(lowerCamelCase__  )]
							return Matrix(lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  )

def 			_snake_case    (					lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int    ,						lowerCamelCase__     :   int  )    ->     Matrix:
							random.seed(lowerCamelCase__  )
							lowerCamelCase_	:							list[list[float]]									=[
							    [random.randint(lowerCamelCase__    ,						lowerCamelCase__  ) for _ in range(lowerCamelCase__  )] for _ in range(lowerCamelCase__  )
							]
							return Matrix(lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  )












"""simple docstring"""



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

							# 1. Validate that path exists between current and next vertices
							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 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   list[int]    ,						lowerCamelCase__     :   int  )    ->     bool:

							# Base Case
							if curr_ind == len(lowerCamelCase__  ):
														# 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(lowerCamelCase__  )  ):
														if valid_connection(lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__    ,						lowerCamelCase__  ):
																					# Insert current vertex  into path as next transition
																					lowerCamelCase_	:							Tuple									=next_ver
																					# Validate created path
																					if util_hamilton_cycle(lowerCamelCase__    ,						lowerCamelCase__    ,						curr_ind + 1  ):
																												return True
																					# Backtrack
																					lowerCamelCase_	:							int									=-1
							return False

def 			_snake_case    (					lowerCamelCase__     :   list[list[int]]    ,						lowerCamelCase__     :   int = 0  )    ->     list[int]:
							lowerCamelCase_	:							Optional[Any]									=[-1] * (len(lowerCamelCase__  ) + 1)
							# initialize start and end of path with starting index
							lowerCamelCase_	:							Optional[int]									=start_index
							# evaluate and if we find answer return path either return empty array
							return path if util_hamilton_cycle(lowerCamelCase__    ,						lowerCamelCase__    ,						1  ) else []



