


'''simple docstring'''


from __future__ import annotations

from typing import Any






class 	lowerCAmelCase__			:




			def __init__(		self  :     List[str]	,  lowerCamelCase__  :     int	,  lowerCamelCase__  :     int	,  lowerCamelCase__  :     float = 0 )   ->None:



					'''simple docstring'''







					_UpperCAmelCase					,    _UpperCAmelCase		:       List[str]								=      row, column
					_UpperCAmelCase		:       List[str]								=      [[default_value for c in range(lowerCamelCase__ )] for r in range(lowerCamelCase__ )]




			def __str__(		self  :     Dict )   ->str:



					'''simple docstring'''







					_UpperCAmelCase		:       Dict								=      F"""Matrix consist of {self.row} rows and {self.column} columns\n"""

					# Make string identifier
					_UpperCAmelCase		:       Optional[Any]								=      0
					for row_vector in self.array:
							for obj in row_vector:
									_UpperCAmelCase		:       Union[str, Any]								=      max(lowerCamelCase__	,  len(str(lowerCamelCase__ ) ) )
					_UpperCAmelCase		:       Tuple								=      F"""%{max_element_length}s"""

					# Make string and return
					def single_line(lowerCamelCase__  :     list[float] ) -> str:
							nonlocal string_format_identifier
							_UpperCAmelCase		:       int								=      "["
							line += ", ".join(string_format_identifier % (obj,) for obj in row_vector )
							line += "]"
							return line

					s += "\n".join(single_line(lowerCamelCase__ ) for row_vector in self.array )
					return s




			def __repr__(		self  :     Any )   ->str:



					'''simple docstring'''







					return str(self )




			def 							lowerCAmelCase__    (		self  :     str	,  lowerCamelCase__  :     tuple[int, int] )   ->bool:



					'''simple docstring'''







					if not (isinstance(lowerCamelCase__	,  (list, tuple) ) and len(lowerCamelCase__ ) == 2):
							return False
					elif not (0 <= loc[0] < self.row and 0 <= loc[1] < self.column):
							return False
					else:
							return True




			def __getitem__(		self  :     Dict	,  lowerCamelCase__  :     tuple[int, int] )   ->Any:



					'''simple docstring'''







					assert self.validate_indicies(lowerCamelCase__ )
					return self.array[loc[0]][loc[1]]




			def __setitem__(		self  :     List[Any]	,  lowerCamelCase__  :     tuple[int, int]	,  lowerCamelCase__  :     float )   ->None:



					'''simple docstring'''







					assert self.validate_indicies(lowerCamelCase__ )
					_UpperCAmelCase		:       Dict								=      value




			def __add__(		self  :     Tuple	,  lowerCamelCase__  :     Matrix )   ->Matrix:



					'''simple docstring'''







					assert isinstance(lowerCamelCase__	,  lowerCamelCase__ )
					assert self.row == another.row and self.column == another.column

					# Add
					_UpperCAmelCase		:       List[str]								=      Matrix(self.row	,  self.column )
					for r in range(self.row ):
							for c in range(self.column ):
									_UpperCAmelCase		:       Any								=      self[r, c] + another[r, c]
					return result




			def __neg__(		self  :     Optional[int] )   ->Matrix:



					'''simple docstring'''







					_UpperCAmelCase		:       Optional[Any]								=      Matrix(self.row	,  self.column )
					for r in range(self.row ):
							for c in range(self.column ):
									_UpperCAmelCase		:       List[Any]								=      -self[r, c]
					return result




			def __sub__(		self  :     List[Any]	,  lowerCamelCase__  :     Matrix )   ->Matrix:



					'''simple docstring'''







					return self + (-another)




			def __mul__(		self  :     Optional[int]	,  lowerCamelCase__  :     int | float | Matrix )   ->Matrix:



					'''simple docstring'''







					if isinstance(lowerCamelCase__	,  (int, float) ):  # Scalar multiplication
							_UpperCAmelCase		:       Optional[Any]								=      Matrix(self.row	,  self.column )
							for r in range(self.row ):
									for c in range(self.column ):
											_UpperCAmelCase		:       List[str]								=      self[r, c] * another
							return result
					elif isinstance(lowerCamelCase__	,  lowerCamelCase__ ):  # Matrix multiplication
							assert self.column == another.row
							_UpperCAmelCase		:       str								=      Matrix(self.row	,  another.column )
							for r in range(self.row ):
									for c in range(another.column ):
											for i in range(self.column ):
													result[r, c] += self[r, i] * another[i, c]
							return result
					else:
							_UpperCAmelCase		:       List[Any]								=      F"""Unsupported type given for another ({type(lowerCamelCase__ )})"""
							raise TypeError(lowerCamelCase__ )




			def 							lowerCAmelCase__    (		self  :     int )   ->Matrix:



					'''simple docstring'''







					_UpperCAmelCase		:       Tuple								=      Matrix(self.column	,  self.row )
					for r in range(self.row ):
							for c in range(self.column ):
									_UpperCAmelCase		:       int								=      self[r, c]
					return result






			def 							lowerCAmelCase__    (		self  :     Any	,  lowerCamelCase__  :     Matrix	,  lowerCamelCase__  :     Matrix )   ->Any:



					'''simple docstring'''







					assert isinstance(lowerCamelCase__	,  lowerCamelCase__ ) and isinstance(lowerCamelCase__	,  lowerCamelCase__ )
					assert self.row == self.column == u.row == v.row  # u, v should be column vector
					assert u.column == v.column == 1  # u, v should be column vector

					# Calculate
					_UpperCAmelCase		:       Optional[int]								=      v.transpose()
					_UpperCAmelCase		:       List[str]								=      (v_t * self * u)[0, 0] + 1
					if numerator_factor == 0:
							return None  # It's not invertable
					return self - ((self * u) * (v_t * self) * (1.0 / numerator_factor))


# Testing
if __name__ == "__main__":






						def  __lowerCAmelCase ():
								# a^(-1)
								_UpperCAmelCase		:       int								=      Matrix(3      , 3      , 0   )
								for i in range(3   ):
										_UpperCAmelCase		:       Union[str, Any]								=      1
								print(F"""a^(-1) is {ainv}"""   )
								# u, v
								_UpperCAmelCase		:       Optional[int]								=      Matrix(3      , 1      , 0   )
								_UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase		:       int								=      1, 2, -3
								_UpperCAmelCase		:       Union[str, Any]								=      Matrix(3      , 1      , 0   )
								_UpperCAmelCase					,    _UpperCAmelCase					,    _UpperCAmelCase		:       Union[str, Any]								=      4, -2, 5
								print(F"""u is {u}"""   )
								print(F"""v is {v}"""   )
								print(F"""uv^T is {u * v.transpose()}"""   )
								# Sherman Morrison
								print(F"""(a + uv^T)^(-1) is {ainv.sherman_morrison(__lowerCAmelCase      , __lowerCAmelCase   )}"""   )






						def  __lowerCAmelCase ():
								import doctest

								doctest.testmod()





						testa()







'''simple docstring'''


def  __lowerCAmelCase (__lowerCAmelCase   ):  # noqa: E741
		_UpperCAmelCase		:       List[str]								=      len(__lowerCAmelCase   )
		_UpperCAmelCase		:       str								=      0
		_UpperCAmelCase		:       List[str]								=      [0] * n
		_UpperCAmelCase		:       int								=      [False] * n
		_UpperCAmelCase		:       Dict								=      [False] * n

		def dfs(__lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase   ):
				if parent == root:
						out_edge_count += 1
				_UpperCAmelCase		:       List[Any]								=      True
				_UpperCAmelCase		:       str								=      at

				for to in l[at]:
						if to == parent:
								pass
						elif not visited[to]:
								_UpperCAmelCase		:       List[str]								=      dfs(__lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase   )
								_UpperCAmelCase		:       Tuple								=      min(low[at]      , low[to]   )

								# AP found via bridge
								if at < low[to]:
										_UpperCAmelCase		:       Dict								=      True
								# AP found via cycle
								if at == low[to]:
										_UpperCAmelCase		:       Dict								=      True
						else:
								_UpperCAmelCase		:       Optional[int]								=      min(low[at]      , __lowerCAmelCase   )
				return out_edge_count

		for i in range(__lowerCAmelCase   ):
				if not visited[i]:
						_UpperCAmelCase		:       str								=      0
						_UpperCAmelCase		:       Tuple								=      dfs(__lowerCAmelCase      , __lowerCAmelCase      , -1      , __lowerCAmelCase   )
						_UpperCAmelCase		:       Optional[int]								=      out_edge_count > 1

		for x in range(len(__lowerCAmelCase   )   ):
				if is_art[x] is True:
						print(__lowerCAmelCase   )


# Adjacency list of graph
lowerCamelCase__    	=     {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 5],
    3: [2, 4],
    4: [3],
    5: [2, 6, 8],
    6: [5, 7],
    7: [6, 8],
    8: [5, 7],
}





compute_ap(data)



