"""simple docstring"""




from __future__ import annotations






def      UpperCAmelCase    (		UpperCamelCase__ = 4 ):






							"""simple docstring"""





							A__		   =							abs(UpperCamelCase__ ) or 4
							return [[1 + x + y * row_size for x in range(UpperCamelCase__ )] for y in range(UpperCamelCase__ )]






def      UpperCAmelCase    (		UpperCamelCase__ ):






							"""simple docstring"""





							return reverse_row(transpose(UpperCamelCase__ ) )
							# OR.. transpose(reverse_column(matrix))






def      UpperCAmelCase    (		UpperCamelCase__ ):






							"""simple docstring"""





							return reverse_row(reverse_column(UpperCamelCase__ ) )
							# OR.. reverse_column(reverse_row(matrix))






def      UpperCAmelCase    (		UpperCamelCase__ ):






							"""simple docstring"""





							return reverse_column(transpose(UpperCamelCase__ ) )
							# OR.. transpose(reverse_row(matrix))






def      UpperCAmelCase    (		UpperCamelCase__ ):






							"""simple docstring"""





							A__		   =							[list(UpperCamelCase__ ) for x in zip(*UpperCamelCase__ )]
							return matrix






def      UpperCAmelCase    (		UpperCamelCase__ ):






							"""simple docstring"""





							A__		   =							matrix[::-1]
							return matrix






def      UpperCAmelCase    (		UpperCamelCase__ ):






							"""simple docstring"""





							A__		   =							[x[::-1] for x in matrix]
							return matrix






def      UpperCAmelCase    (		UpperCamelCase__ ):






							"""simple docstring"""





							for i in matrix:
														print(*UpperCamelCase__ )


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

				__lowerCamelCase							 =     make_matrix()
				print("\norigin:\n")
				print_matrix(matrix)
				print("\nrotate 180:\n")
				print_matrix(rotate_aaa(matrix))

				__lowerCamelCase							 =     make_matrix()
				print("\norigin:\n")
				print_matrix(matrix)
				print("\nrotate 270 counterclockwise:\n")
				print_matrix(rotate_aaa(matrix))






"""simple docstring"""




from __future__ import annotations

from typing import Generic, TypeVar

__lowerCamelCase							 =     TypeVar("T")
class 			UpperCamelCase__(	Generic[T]       ):





						def __init__(				self						,__UpperCAmelCase   )    -> None:
													A__		   =							data
													A__		   =							self
													A__		   =							0






class 			UpperCamelCase__(	Generic[T]       ):





						def __init__(				self   )    -> None:
													# map from node name to the node object
													A__		   =							{}





						def  snake_case__		(				self						,__UpperCAmelCase   )    -> None:
													# create a new set with x as its member
													A__		   =							DisjointSetTreeNode(__UpperCAmelCase   )





						def  snake_case__		(				self						,__UpperCAmelCase   )    -> DisjointSetTreeNode[T]:
													# find the set x belongs to (with path-compression)
													A__		   =							self.map[data]
													if elem_ref != elem_ref.parent:
																				A__		   =							self.find_set(elem_ref.parent.data   )
													return elem_ref.parent





						def  snake_case__		(				self						,__UpperCAmelCase						,__UpperCAmelCase   )    -> None:
													# helper function for union operation
													if nodea.rank > nodea.rank:
																				A__		   =							nodea
													else:
																				A__		   =							nodea
																				if nodea.rank == nodea.rank:
																											nodea.rank += 1





						def  snake_case__		(				self						,__UpperCAmelCase						,__UpperCAmelCase   )    -> None:
													# merge 2 disjoint sets
													self.link(self.find_set(__UpperCAmelCase   )						,self.find_set(__UpperCAmelCase   )   )






class 			UpperCamelCase__(	Generic[T]       ):





						def __init__(				self   )    -> None:
													# connections: map from the node to the neighbouring nodes (with weights)
													A__		   =							{}





						def  snake_case__		(				self						,__UpperCAmelCase   )    -> None:
													# add a node ONLY if its not present in the graph
													if node not in self.connections:
																				A__		   =							{}





						def  snake_case__		(				self						,__UpperCAmelCase						,__UpperCAmelCase						,__UpperCAmelCase   )    -> None:
													# add an edge with the given weight
													self.add_node(__UpperCAmelCase   )
													self.add_node(__UpperCAmelCase   )
													A__		   =							weight
													A__		   =							weight





						def  snake_case__		(				self   )    -> GraphUndirectedWeighted[T]:
													A__		   =							[]
													A__		   =							set()
													for start in self.connections:
																				for end in self.connections[start]:
																											if (start, end) not in seen:
																																		seen.add((end, start)   )
																																		edges.append((start, end, self.connections[start][end])   )
													edges.sort(key=lambda __UpperCAmelCase   : x[2]   )

													# creating the disjoint set
													A__		   =							DisjointSetTree[T]()
													for node in self.connections:
																				disjoint_set.make_set(__UpperCAmelCase   )

													# MST generation
													A__		   =							0
													A__		   =							0
													A__		   =							GraphUndirectedWeighted[T]()
													while num_edges < len(self.connections   ) - 1:
																				A__   ,     A__   ,     A__		   =							edges[index]
																				index += 1
																				A__		   =							disjoint_set.find_set(__UpperCAmelCase   )
																				A__		   =							disjoint_set.find_set(__UpperCAmelCase   )
																				if parent_u != parent_v:
																											num_edges += 1
																											graph.add_edge(__UpperCAmelCase						,__UpperCAmelCase						,__UpperCAmelCase   )
																											disjoint_set.union(__UpperCAmelCase						,__UpperCAmelCase   )
													return graph





