
"""simple docstring"""


import gc
import unittest

import torch
from parameterized import parameterized

from diffusers import AutoencoderKL
from diffusers.utils import floats_tensor, load_hf_numpy, require_torch_gpu, slow, torch_all_close, torch_device
from diffusers.utils.import_utils import is_xformers_available
from diffusers.utils.testing_utils import enable_full_determinism

from .test_modeling_common import ModelTesterMixin, UNetTesterMixin


enable_full_determinism()







class 				lowerCAmelCase_				(      __lowerCAmelCase		,					__lowerCAmelCase		,					unittest.TestCase    ):



						'''simple docstring'''


						_lowerCamelCase:    int      =    AutoencoderKL
						_lowerCamelCase:    Union[str, Any]      =    '''sample'''
						_lowerCamelCase:    int      =    1E-2


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Any:
								A						   =   4
								A						   =   3
								A						   =   (32, 32)

								A						   =   floats_tensor((batch_size, num_channels) + sizes      ).to(lowerCAmelCase_      )

								return {"sample": image}


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   List[str]:
								return (3, 32, 32)


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   int:
								return (3, 32, 32)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Any:
								A						   =   {
								    'block_out_channels': [32, 64],
								    'in_channels': 3,
								    'out_channels': 3,
								    'down_block_types': ['DownEncoderBlock2D', 'DownEncoderBlock2D'],
								    'up_block_types': ['UpDecoderBlock2D', 'UpDecoderBlock2D'],
								    'latent_channels': 4,
								}
								A						   =   self.dummy_input
								return init_dict, inputs_dict


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   List[Any]:
								pass


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Tuple:
								pass


						@unittest.skipIf(torch_device == 'mps'  ,'Gradient checkpointing skipped on MPS'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   Optional[int]:
								# enable deterministic behavior for gradient checkpointing
								A   ,      A						   =   self.prepare_init_args_and_inputs_for_common()
								A						   =   self.model_class(**lowerCAmelCase_      )
								model.to(lowerCAmelCase_      )

								assert not model.is_gradient_checkpointing and model.training

								A						   =   model(**lowerCAmelCase_      ).sample
								# run the backwards pass on the model. For backwards pass, for simplicity purpose,
								# we won't calculate the loss and rather backprop on out.sum()
								model.zero_grad()

								A						   =   torch.randn_like(lowerCAmelCase_      )
								A						   =   (out - labels).mean()
								loss.backward()

								# re-instantiate the model now enabling gradient checkpointing
								A						   =   self.model_class(**lowerCAmelCase_      )
								# clone model
								model_a.load_state_dict(model.state_dict()      )
								model_a.to(lowerCAmelCase_      )
								model_a.enable_gradient_checkpointing()

								assert model_a.is_gradient_checkpointing and model_a.training

								A						   =   model_a(**lowerCAmelCase_      ).sample
								# run the backwards pass on the model. For backwards pass, for simplicity purpose,
								# we won't calculate the loss and rather backprop on out.sum()
								model_a.zero_grad()
								A						   =   (out_a - labels).mean()
								loss_a.backward()

								# compare the output and parameters gradients
								self.assertTrue((loss - loss_a).abs() < 1e-5      )
								A						   =   dict(model.named_parameters()      )
								A						   =   dict(model_a.named_parameters()      )
								for name, param in named_params.items():
										self.assertTrue(torch_all_close(param.grad.data  ,named_params_a[name].grad.data  ,atol=5e-5      )      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   Union[str, Any]:
								A   ,      A						   =   AutoencoderKL.from_pretrained('fusing/autoencoder-kl-dummy'  ,output_loading_info=lowerCAmelCase_      )
								self.assertIsNotNone(lowerCAmelCase_      )
								self.assertEqual(len(loading_info['missing_keys']      )  ,0      )

								model.to(lowerCAmelCase_      )
								A						   =   model(**self.dummy_input      )

								assert image is not None, "Make sure output is not None"




						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
								A						   =   AutoencoderKL.from_pretrained('fusing/autoencoder-kl-dummy'      )
								A						   =   model.to(lowerCAmelCase_      )
								model.eval()

								if torch_device == "mps":
										A						   =   torch.manual_seed(0      )
								else:
										A						   =   torch.Generator(device=lowerCAmelCase_      ).manual_seed(0      )

								A						   =   torch.randn(
								    1  ,model.config.in_channels  ,model.config.sample_size  ,model.config.sample_size  ,generator=torch.manual_seed(0      )  ,)
								A						   =   image.to(lowerCAmelCase_      )
								with torch.no_grad():
										A						   =   model(lowerCAmelCase_  ,sample_posterior=lowerCAmelCase_  ,generator=lowerCAmelCase_      ).sample

								A						   =   output[0, -1, -3:, -3:].flatten().cpu()

								# Since the VAE Gaussian prior's generator is seeded on the appropriate device,
								# the expected output slices are not the same for CPU and GPU.
								if torch_device == "mps":
										A						   =   torch.tensor(
										    [
										        -4.0_078e-01,
										        -3.8_323e-04,
										        -1.2_681e-01,
										        -1.1_462e-01,
										        2.0_095e-01,
										        1.0_893e-01,
										        -8.8_247e-02,
										        -3.0_361e-01,
										        -9.8_644e-03,
										    ]      )
								elif torch_device == "cpu":
										A						   =   torch.tensor(
										    [-0.13_52, 0.08_78, 0.04_19, -0.08_18, -0.10_69, 0.06_88, -0.14_58, -0.44_46, -0.00_26]      )
								else:
										A						   =   torch.tensor(
										    [-0.24_21, 0.46_42, 0.25_07, -0.04_38, 0.06_82, 0.31_60, -0.20_18, -0.07_27, 0.24_85]      )

								self.assertTrue(torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,rtol=1e-2      )      )







@slow
class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      Optional[Any]  ,A_     :      Optional[Any]      )     ->   List[Any]:
								return F'gaussian_noise_s={seed}_shape={"_".join([str(lowerCAmelCase_      ) for s in shape]      )}.npy'


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   Optional[int]:
								# clean up the VRAM after each test
								super().tearDown()
								gc.collect()
								torch.cuda.empty_cache()


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple  ,A_     :      Optional[int]=0  ,A_     :      Tuple=(4, 3, 512, 512)  ,A_     :      List[Any]=False      )     ->   Any:
								A						   =   torch.floataa if fpaa else torch.floataa
								A						   =   torch.from_numpy(load_hf_numpy(self.get_file_format(lowerCAmelCase_  ,lowerCAmelCase_      )      )      ).to(lowerCAmelCase_      ).to(lowerCAmelCase_      )
								return image


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,A_     :      Union[str, Any]="CompVis/stable-diffusion-v1-4"  ,A_     :      Optional[int]=False      )     ->   int:
								A						   =   'fp16' if fpaa else None
								A						   =   torch.floataa if fpaa else torch.floataa

								A						   =   AutoencoderKL.from_pretrained(
								    lowerCAmelCase_  ,subfolder='vae'  ,torch_dtype=lowerCAmelCase_  ,revision=lowerCAmelCase_  ,)
								model.to(lowerCAmelCase_      ).eval()

								return model


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      List[Any]=0      )     ->   int:
								if torch_device == "mps":
										return torch.manual_seed(lowerCAmelCase_      )
								return torch.Generator(device=lowerCAmelCase_      ).manual_seed(lowerCAmelCase_      )


						@parameterized.expand(
						    [
						        # fmt: off
						        [33, [-0.16_03, 0.98_78, -0.04_95, -0.07_90, -0.27_09, 0.83_75, -0.20_60, -0.08_24], [-0.23_95, 0.00_98, 0.01_02, -0.07_09, -0.28_40, -0.02_74, -0.07_18, -0.18_24]],
						        [47, [-0.23_76, 0.11_68, 0.13_32, -0.48_40, -0.25_08, -0.07_91, -0.04_93, -0.40_89], [0.03_50, 0.08_47, 0.04_67, 0.03_44, -0.08_42, -0.05_47, -0.06_33, -0.11_31]],
						        # fmt: on
						    ]      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Dict  ,A_     :      Any  ,A_     :      Union[str, Any]      )     ->   Tuple:
								A						   =   self.get_sd_vae_model()
								A						   =   self.get_sd_image(lowerCAmelCase_      )
								A						   =   self.get_generator(lowerCAmelCase_      )

								with torch.no_grad():
										A						   =   model(lowerCAmelCase_  ,generator=lowerCAmelCase_  ,sample_posterior=lowerCAmelCase_      ).sample

								assert sample.shape == image.shape

								A						   =   sample[-1, -2:, -2:, :2].flatten().float().cpu()
								A						   =   torch.tensor(expected_slice_mps if torch_device == 'mps' else expected_slice      )

								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=3e-3      )


						@parameterized.expand(
						    [
						        # fmt: off
						        [33, [-0.05_13, 0.02_89, 1.37_99, 0.21_66, -0.25_73, -0.08_71, 0.51_03, -0.09_99]],
						        [47, [-0.41_28, -0.13_20, -0.37_04, 0.19_65, -0.41_16, -0.23_32, -0.33_40, 0.22_47]],
						        # fmt: on
						    ]      )
						@require_torch_gpu
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Optional[int]  ,A_     :      Union[str, Any]      )     ->   Optional[int]:
								A						   =   self.get_sd_vae_model(fpaa=lowerCAmelCase_      )
								A						   =   self.get_sd_image(lowerCAmelCase_  ,fpaa=lowerCAmelCase_      )
								A						   =   self.get_generator(lowerCAmelCase_      )

								with torch.no_grad():
										A						   =   model(lowerCAmelCase_  ,generator=lowerCAmelCase_  ,sample_posterior=lowerCAmelCase_      ).sample

								assert sample.shape == image.shape

								A						   =   sample[-1, -2:, :2, -2:].flatten().float().cpu()
								A						   =   torch.tensor(lowerCAmelCase_      )

								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=1e-2      )


						@parameterized.expand(
						    [
						        # fmt: off
						        [33, [-0.16_09, 0.98_66, -0.04_87, -0.07_77, -0.27_16, 0.83_68, -0.20_55, -0.08_14], [-0.23_95, 0.00_98, 0.01_02, -0.07_09, -0.28_40, -0.02_74, -0.07_18, -0.18_24]],
						        [47, [-0.23_77, 0.11_47, 0.13_33, -0.48_41, -0.25_06, -0.08_05, -0.04_91, -0.40_85], [0.03_50, 0.08_47, 0.04_67, 0.03_44, -0.08_42, -0.05_47, -0.06_33, -0.11_31]],
						        # fmt: on
						    ]      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      int  ,A_     :      Dict  ,A_     :      Any  ,A_     :      Tuple      )     ->   Any:
								A						   =   self.get_sd_vae_model()
								A						   =   self.get_sd_image(lowerCAmelCase_      )

								with torch.no_grad():
										A						   =   model(lowerCAmelCase_      ).sample

								assert sample.shape == image.shape

								A						   =   sample[-1, -2:, -2:, :2].flatten().float().cpu()
								A						   =   torch.tensor(expected_slice_mps if torch_device == 'mps' else expected_slice      )

								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=3e-3      )


						@parameterized.expand(
						    [
						        # fmt: off
						        [13, [-0.20_51, -0.18_03, -0.23_11, -0.21_14, -0.32_92, -0.35_74, -0.29_53, -0.33_23]],
						        [37, [-0.26_32, -0.26_25, -0.21_99, -0.27_41, -0.45_39, -0.49_90, -0.37_20, -0.49_25]],
						        # fmt: on
						    ]      )
						@require_torch_gpu
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple  ,A_     :      Tuple  ,A_     :      Any      )     ->   Any:
								A						   =   self.get_sd_vae_model()
								A						   =   self.get_sd_image(lowerCAmelCase_  ,shape=(3, 4, 64, 64)      )

								with torch.no_grad():
										A						   =   model.decode(lowerCAmelCase_      ).sample

								assert list(sample.shape      ) == [3, 3, 512, 512]

								A						   =   sample[-1, -2:, :2, -2:].flatten().cpu()
								A						   =   torch.tensor(lowerCAmelCase_      )

								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=1e-3      )


						@parameterized.expand(
						    [
						        # fmt: off
						        [27, [-0.03_69, 0.02_07, -0.07_76, -0.06_82, -0.17_47, -0.19_30, -0.14_65, -0.20_39]],
						        [16, [-0.16_28, -0.21_34, -0.27_47, -0.26_42, -0.37_74, -0.44_04, -0.36_87, -0.42_77]],
						        # fmt: on
						    ]      )
						@require_torch_gpu
						def 						_SCREAMING_SNAKE_CASE      ( self     :      int  ,A_     :      Optional[int]  ,A_     :      List[Any]      )     ->   Optional[int]:
								A						   =   self.get_sd_vae_model(fpaa=lowerCAmelCase_      )
								A						   =   self.get_sd_image(lowerCAmelCase_  ,shape=(3, 4, 64, 64)  ,fpaa=lowerCAmelCase_      )

								with torch.no_grad():
										A						   =   model.decode(lowerCAmelCase_      ).sample

								assert list(sample.shape      ) == [3, 3, 512, 512]

								A						   =   sample[-1, -2:, :2, -2:].flatten().float().cpu()
								A						   =   torch.tensor(lowerCAmelCase_      )

								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=5e-3      )


						@parameterized.expand([(13,), (16,), (27,)]      )
						@require_torch_gpu
						@unittest.skipIf(not is_xformers_available()  ,reason='xformers is not required when using PyTorch 2.0.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Union[str, Any]      )     ->   Optional[Any]:
								A						   =   self.get_sd_vae_model(fpaa=lowerCAmelCase_      )
								A						   =   self.get_sd_image(lowerCAmelCase_  ,shape=(3, 4, 64, 64)  ,fpaa=lowerCAmelCase_      )

								with torch.no_grad():
										A						   =   model.decode(lowerCAmelCase_      ).sample

								model.enable_xformers_memory_efficient_attention()
								with torch.no_grad():
										A						   =   model.decode(lowerCAmelCase_      ).sample

								assert list(sample.shape      ) == [3, 3, 512, 512]

								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=1e-1      )


						@parameterized.expand([(13,), (16,), (37,)]      )
						@require_torch_gpu
						@unittest.skipIf(not is_xformers_available()  ,reason='xformers is not required when using PyTorch 2.0.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,A_     :      Union[str, Any]      )     ->   int:
								A						   =   self.get_sd_vae_model()
								A						   =   self.get_sd_image(lowerCAmelCase_  ,shape=(3, 4, 64, 64)      )

								with torch.no_grad():
										A						   =   model.decode(lowerCAmelCase_      ).sample

								model.enable_xformers_memory_efficient_attention()
								with torch.no_grad():
										A						   =   model.decode(lowerCAmelCase_      ).sample

								assert list(sample.shape      ) == [3, 3, 512, 512]

								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=1e-2      )




						@parameterized.expand(
						    [
						        # fmt: off
						        [33, [-0.30_01, 0.09_18, -2.69_84, -3.97_20, -3.20_99, -5.03_53, 1.73_38, -0.20_65, 3.42_67]],
						        [47, [-1.50_30, -4.38_71, -6.03_55, -9.11_57, -1.66_61, -2.78_53, 2.16_07, -5.08_23, 2.56_33]],
						        # fmt: on
						    ]      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple  ,A_     :      List[str]  ,A_     :      str      )     ->   Tuple:
								A						   =   self.get_sd_vae_model()
								A						   =   self.get_sd_image(lowerCAmelCase_      )
								A						   =   self.get_generator(lowerCAmelCase_      )

								with torch.no_grad():
										A						   =   model.encode(lowerCAmelCase_      ).latent_dist
										A						   =   dist.sample(generator=lowerCAmelCase_      )

								assert list(sample.shape      ) == [image.shape[0], 4] + [i // 8 for i in image.shape[2:]]

								A						   =   sample[0, -1, -3:, -3:].flatten().cpu()
								A						   =   torch.tensor(lowerCAmelCase_      )

								A						   =   3e-3 if torch_device != 'mps' else 1e-2
								assert torch_all_close(lowerCAmelCase_  ,lowerCAmelCase_  ,atol=lowerCAmelCase_      )

"""simple docstring"""


import sys
from collections import defaultdict







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      Optional[Any]      )     ->   int:
							A						   =   []


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      int      )     ->   Optional[int]:
							return self.node_position[vertex]


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      List[Any]  ,A_     :      Any      )     ->   List[Any]:
							A						   =   pos


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      str  ,A_     :      str  ,A_     :      Dict  ,A_     :      List[str]      )     ->   str:
							if start > size // 2 - 1:
								return
							else:
								if 2 * start + 2 >= size:
									A						   =   2 * start + 1
								else:
									if heap[2 * start + 1] < heap[2 * start + 2]:
										A						   =   2 * start + 1
									else:
										A						   =   2 * start + 2
								if heap[smallest_child] < heap[start]:
									A   ,      A						   =   heap[smallest_child], positions[smallest_child]
									A   ,      A						   =   (
									    heap[start],
									    positions[start],
									)
									A   ,      A						   =   temp, tempa

									A						   =   self.get_position(positions[smallest_child]      )
									self.set_position(
									    positions[smallest_child]  ,self.get_position(positions[start]      )      )
									self.set_position(positions[start]  ,A_      )

									self.top_to_bottom(A_  ,A_  ,A_  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      Optional[int]  ,A_     :      Dict  ,A_     :      str  ,A_     :      Union[str, Any]      )     ->   Dict:
							A						   =   position[index]

							while index != 0:
								A						   =   int((index - 2) / 2      ) if index % 2 == 0 else int((index - 1) / 2      )

								if val < heap[parent]:
									A						   =   heap[parent]
									A						   =   position[parent]
									self.set_position(position[parent]  ,A_      )
								else:
									A						   =   val
									A						   =   temp
									self.set_position(A_  ,A_      )
									break
								A						   =   parent
							else:
								A						   =   val
								A						   =   temp
								self.set_position(A_  ,0      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Tuple  ,A_     :      Dict      )     ->   Union[str, Any]:
							A						   =   len(A_      ) // 2 - 1
							for i in range(A_  ,-1  ,-1      ):
								self.top_to_bottom(A_  ,A_  ,len(A_      )  ,A_      )




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[int]  ,A_     :      Dict      )     ->   Union[str, Any]:
							A						   =   positions[0]
							A						   =   sys.maxsize
							self.top_to_bottom(A_  ,0  ,len(A_      )  ,A_      )
							return temp






def       _snake_case				(		snake_case__   :     Dict     ):
	A						   =   Heap()

	A						   =   [0] * len(snake_case__     )
	A						   =   [-1] * len(snake_case__     )  # Neighboring Tree Vertex of selected vertex
	# Minimum Distance of explored vertex with neighboring vertex of partial tree
	# formed in graph
	A						   =   []  # Heap of Distance of vertices from their neighboring vertex
	A						   =   []

	for vertex in range(len(snake_case__     )     ):
		distance_tv.append(sys.maxsize     )
		positions.append(snake_case__     )
		heap.node_position.append(snake_case__     )

	A						   =   []
	A						   =   1
	A						   =   sys.maxsize
	for neighbor, distance in adjacency_list[0]:
		A						   =   0
		A						   =   distance
	heap.heapify(snake_case__	,      snake_case__     )

	for _ in range(1	,      len(snake_case__     )     ):
		A						   =   heap.delete_minimum(snake_case__	,      snake_case__     )
		if visited[vertex] == 0:
			tree_edges.append((nbr_tv[vertex], vertex)     )
			A						   =   1
			for neighbor, distance in adjacency_list[vertex]:
				if (
				    visited[neighbor] == 0
				    and distance < distance_tv[heap.get_position(snake_case__     )]
				):
					A						   =   distance
					heap.bottom_to_top(
					    snake_case__	,      heap.get_position(snake_case__     )	,      snake_case__	,      snake_case__     )
					A						   =   vertex
	return tree_edges


if __name__ == "__main__":  # pragma: no cover
		# < --------- Prims Algorithm --------- >
		_lowercase							   =				int(input('''Enter number of edges: ''').strip())
		_lowercase							   =				defaultdict(list)
		for _ in range(edges_number):
				_lowercase							   =				[int(x) for x in input().strip().split()]
				adjacency_list[edge[0]].append([edge[1], edge[2]])
				adjacency_list[edge[1]].append([edge[0], edge[2]])
		print(prisms_algorithm(adjacency_list))