



import heapq as hq
import math
from collections.abc import Iterator


class   __lowerCAmelCase  :
					"""simple docstring"""






					def __init__(  self       :							List[Any]					,       _snake_case       :							Tuple       ):






								"""simple docstring"""


								A__	  =     str(id_       )
								A__	  =     None
								A__	  =     None
								A__	  =     []
								A__	  =     {}  # {vertex:distance}



					def __lt__(  self       :							List[str]					,       _snake_case       :							Tuple       ):






								"""simple docstring"""


								return self.key < other.key



					def __repr__(  self       :							int       ):






								"""simple docstring"""


								return self.id



					def      _a				(  self       :							str					,       _snake_case       :							str       ):






								"""simple docstring"""


								self.neighbors.append(_snake_case       )



					def      _a				(  self       :							Tuple					,       _snake_case       :							str					,       _snake_case       :							Optional[Any]       ):






								"""simple docstring"""


								A__	  =     weight







def A    (							__UpperCamelCase			,						__UpperCamelCase			,						__UpperCamelCase			,						__UpperCamelCase       )    ->   Tuple:
			# add the neighbors:
			graph[a - 1].add_neighbor(graph[b - 1]       )
			graph[b - 1].add_neighbor(graph[a - 1]       )
			# add the edges:
			graph[a - 1].add_edge(graph[b - 1]			,						__UpperCamelCase       )
			graph[b - 1].add_edge(graph[a - 1]			,						__UpperCamelCase       )


def A    (							__UpperCamelCase			,						__UpperCamelCase       )    ->   list:
			A__	  =     []
			for u in graph:
						A__	  =     math.inf
						A__	  =     None
			A__	  =     0
			A__	  =     graph[:]
			while q:
						A__	  =     min(__UpperCamelCase       )
						q.remove(__UpperCamelCase       )
						for v in u.neighbors:
									if (v in q) and (u.edges[v.id] < v.key):
												A__	  =     u
												A__	  =     u.edges[v.id]
			for i in range(1			,						len(__UpperCamelCase       )       ):
						a.append((int(graph[i].id       ) + 1, int(graph[i].pi.id       ) + 1)       )
			return a


def A    (							__UpperCamelCase			,						__UpperCamelCase       )    ->   Iterator[tuple]:
			for u in graph:
						A__	  =     math.inf
						A__	  =     None
			A__	  =     0

			A__	  =     list(__UpperCamelCase       )
			hq.heapify(__UpperCamelCase       )

			while h:
						A__	  =     hq.heappop(__UpperCamelCase       )
						for v in u.neighbors:
									if (v in h) and (u.edges[v.id] < v.key):
												A__	  =     u
												A__	  =     u.edges[v.id]
												hq.heapify(__UpperCamelCase       )

			for i in range(1			,						len(__UpperCamelCase       )       ):
						yield (int(graph[i].id       ) + 1, int(graph[i].pi.id       ) + 1)


def A    (							)    ->   None:
			pass


if __name__ == "__main__":
							import doctest

							doctest.testmod()









from __future__ import annotations


def A    (							__UpperCamelCase = 4       )    ->   list[list[int]]:
			A__	  =     abs(__UpperCamelCase       ) or 4
			return [[1 + x + y * row_size for x in range(__UpperCamelCase       )] for y in range(__UpperCamelCase       )]


def A    (							__UpperCamelCase       )    ->   list[list[int]]:
			return reverse_row(transpose(__UpperCamelCase       )       )
			# OR.. transpose(reverse_column(matrix))


def A    (							__UpperCamelCase       )    ->   list[list[int]]:
			return reverse_row(reverse_column(__UpperCamelCase       )       )
			# OR.. reverse_column(reverse_row(matrix))


def A    (							__UpperCamelCase       )    ->   list[list[int]]:
			return reverse_column(transpose(__UpperCamelCase       )       )
			# OR.. transpose(reverse_row(matrix))


def A    (							__UpperCamelCase       )    ->   list[list[int]]:
			A__	  =     [list(__UpperCamelCase       ) for x in zip(*__UpperCamelCase       )]
			return matrix


def A    (							__UpperCamelCase       )    ->   list[list[int]]:
			A__	  =     matrix[::-1]
			return matrix


def A    (							__UpperCamelCase       )    ->   list[list[int]]:
			A__	  =     [x[::-1] for x in matrix]
			return matrix


def A    (							__UpperCamelCase       )    ->   None:
			for i in matrix:
						print(*__UpperCamelCase       )


if __name__ == "__main__":
							SCREAMING_SNAKE_CASE__   			=   make_matrix()
							print('''\norigin:\n''')
							print_matrix(matrix)
							print('''\nrotate 90 counterclockwise:\n''')
							print_matrix(rotate_aa(matrix))

							SCREAMING_SNAKE_CASE__   			=   make_matrix()
							print('''\norigin:\n''')
							print_matrix(matrix)
							print('''\nrotate 180:\n''')
							print_matrix(rotate_aaa(matrix))

							SCREAMING_SNAKE_CASE__   			=   make_matrix()
							print('''\norigin:\n''')
							print_matrix(matrix)
							print('''\nrotate 270 counterclockwise:\n''')
							print_matrix(rotate_aaa(matrix))




