





'''simple docstring'''

import gc
import random
import unittest

import numpy as np
import torch
from PIL import Image
from transformers import CLIPTextConfig, CLIPTextModel, CLIPTokenizer

from diffusers import AutoencoderKL, DDIMScheduler, DDPMScheduler, StableDiffusionUpscalePipeline, UNetaDConditionModel
from diffusers.utils import floats_tensor, load_image, load_numpy, slow, torch_device
from diffusers.utils.testing_utils import enable_full_determinism, require_torch_gpu


enable_full_determinism()







class __a(   unittest.TestCase			):





   def      UpperCAmelCase__     (					self				:			str    ):

      '''simple docstring'''

      super().tearDown()
      gc.collect()
      torch.cuda.empty_cache()





   @property
   def      UpperCAmelCase__     (					self				:			Optional[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       1
      __SCREAMING_SNAKE_CASE      							=       3
      __SCREAMING_SNAKE_CASE      							=       (32, 32)

      __SCREAMING_SNAKE_CASE      							=       floats_tensor((batch_size, num_channels) + sizes				,rng=random.Random(0    )    ).to(lowerCamelCase    )
      return image





   @property
   def      UpperCAmelCase__     (					self				:			Union[str, Any]    ):

      '''simple docstring'''

      torch.manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       UNetaDConditionModel(
          block_out_channels=(32, 32, 64)				,layers_per_block=2				,sample_size=32				,in_channels=7				,out_channels=4				,down_block_types=("""DownBlock2D""", """CrossAttnDownBlock2D""", """CrossAttnDownBlock2D""")				,up_block_types=("""CrossAttnUpBlock2D""", """CrossAttnUpBlock2D""", """UpBlock2D""")				,cross_attention_dim=32				,attention_head_dim=8				,use_linear_projection=lowerCamelCase				,only_cross_attention=(True, True, False)				,num_class_embeds=100				,)
      return model





   @property
   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      torch.manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       AutoencoderKL(
          block_out_channels=[32, 32, 64]				,in_channels=3				,out_channels=3				,down_block_types=["""DownEncoderBlock2D""", """DownEncoderBlock2D""", """DownEncoderBlock2D"""]				,up_block_types=["""UpDecoderBlock2D""", """UpDecoderBlock2D""", """UpDecoderBlock2D"""]				,latent_channels=4				,)
      return model





   @property
   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      torch.manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       CLIPTextConfig(
          bos_token_id=0				,eos_token_id=2				,hidden_size=32				,intermediate_size=37				,layer_norm_eps=1E-0_5				,num_attention_heads=4				,num_hidden_layers=5				,pad_token_id=1				,vocab_size=1000				,hidden_act="""gelu"""				,projection_dim=512				,)
      return CLIPTextModel(lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Optional[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       """cpu"""  # ensure determinism for the device-dependent torch.Generator
      __SCREAMING_SNAKE_CASE      							=       self.dummy_cond_unet_upscale
      __SCREAMING_SNAKE_CASE      							=       DDPMScheduler()
      __SCREAMING_SNAKE_CASE      							=       DDIMScheduler(prediction_type="""v_prediction"""    )
      __SCREAMING_SNAKE_CASE      							=       self.dummy_vae
      __SCREAMING_SNAKE_CASE      							=       self.dummy_text_encoder
      __SCREAMING_SNAKE_CASE      							=       CLIPTokenizer.from_pretrained("""hf-internal-testing/tiny-random-clip"""    )

      __SCREAMING_SNAKE_CASE      							=       self.dummy_image.cpu().permute(0				,2				,3				,1    )[0]
      __SCREAMING_SNAKE_CASE      							=       Image.fromarray(np.uinta(lowerCamelCase    )    ).convert("""RGB"""    ).resize((64, 64)    )

      # make sure here that pndm scheduler skips prk
      __SCREAMING_SNAKE_CASE      							=       StableDiffusionUpscalePipeline(
          unet=lowerCamelCase				,low_res_scheduler=lowerCamelCase				,scheduler=lowerCamelCase				,vae=lowerCamelCase				,text_encoder=lowerCamelCase				,tokenizer=lowerCamelCase				,max_noise_level=350				,)
      __SCREAMING_SNAKE_CASE      							=       sd_pipe.to(lowerCamelCase    )
      sd_pipe.set_progress_bar_config(disable=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       """A painting of a squirrel eating a burger"""
      __SCREAMING_SNAKE_CASE      							=       torch.Generator(device=lowerCamelCase    ).manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       sd_pipe(
          [prompt]				,image=lowerCamelCase				,generator=lowerCamelCase				,guidance_scale=6.0				,noise_level=20				,num_inference_steps=2				,output_type="""np"""				,)

      __SCREAMING_SNAKE_CASE      							=       output.images

      __SCREAMING_SNAKE_CASE      							=       torch.Generator(device=lowerCamelCase    ).manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       sd_pipe(
          [prompt]				,image=lowerCamelCase				,generator=lowerCamelCase				,guidance_scale=6.0				,noise_level=20				,num_inference_steps=2				,output_type="""np"""				,return_dict=lowerCamelCase				,)[0]

      __SCREAMING_SNAKE_CASE      							=       image[0, -3:, -3:, -1]
      __SCREAMING_SNAKE_CASE      							=       image_from_tuple[0, -3:, -3:, -1]

      __SCREAMING_SNAKE_CASE      							=       low_res_image.size[0] * 4
      assert image.shape == (1, expected_height_width, expected_height_width, 3)
      __SCREAMING_SNAKE_CASE      							=       np.array([0.3_113, 0.3_910, 0.4_272, 0.4_859, 0.5_061, 0.4_652, 0.5_362, 0.5_715, 0.5_661]    )

      assert np.abs(image_slice.flatten() - expected_slice    ).max() < 1E-2
      assert np.abs(image_from_tuple_slice.flatten() - expected_slice    ).max() < 1E-2





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       """cpu"""  # ensure determinism for the device-dependent torch.Generator
      __SCREAMING_SNAKE_CASE      							=       self.dummy_cond_unet_upscale
      __SCREAMING_SNAKE_CASE      							=       DDPMScheduler()
      __SCREAMING_SNAKE_CASE      							=       DDIMScheduler(prediction_type="""v_prediction"""    )
      __SCREAMING_SNAKE_CASE      							=       self.dummy_vae
      __SCREAMING_SNAKE_CASE      							=       self.dummy_text_encoder
      __SCREAMING_SNAKE_CASE      							=       CLIPTokenizer.from_pretrained("""hf-internal-testing/tiny-random-clip"""    )

      __SCREAMING_SNAKE_CASE      							=       self.dummy_image.cpu().permute(0				,2				,3				,1    )[0]
      __SCREAMING_SNAKE_CASE      							=       Image.fromarray(np.uinta(lowerCamelCase    )    ).convert("""RGB"""    ).resize((64, 64)    )

      # make sure here that pndm scheduler skips prk
      __SCREAMING_SNAKE_CASE      							=       StableDiffusionUpscalePipeline(
          unet=lowerCamelCase				,low_res_scheduler=lowerCamelCase				,scheduler=lowerCamelCase				,vae=lowerCamelCase				,text_encoder=lowerCamelCase				,tokenizer=lowerCamelCase				,max_noise_level=350				,)
      __SCREAMING_SNAKE_CASE      							=       sd_pipe.to(lowerCamelCase    )
      sd_pipe.set_progress_bar_config(disable=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       """A painting of a squirrel eating a burger"""
      __SCREAMING_SNAKE_CASE      							=       sd_pipe(
          2 * [prompt]				,image=2 * [low_res_image]				,guidance_scale=6.0				,noise_level=20				,num_inference_steps=2				,output_type="""np"""				,)
      __SCREAMING_SNAKE_CASE      							=       output.images
      assert image.shape[0] == 2

      __SCREAMING_SNAKE_CASE      							=       torch.Generator(device=lowerCamelCase    ).manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       sd_pipe(
          [prompt]				,image=lowerCamelCase				,generator=lowerCamelCase				,num_images_per_prompt=2				,guidance_scale=6.0				,noise_level=20				,num_inference_steps=2				,output_type="""np"""				,)
      __SCREAMING_SNAKE_CASE      							=       output.images
      assert image.shape[0] == 2





   @unittest.skipIf(torch_device != """cuda"""				,"""This test requires a GPU"""    )
   def      UpperCAmelCase__     (					self				:			Union[str, Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.dummy_cond_unet_upscale
      __SCREAMING_SNAKE_CASE      							=       DDPMScheduler()
      __SCREAMING_SNAKE_CASE      							=       DDIMScheduler(prediction_type="""v_prediction"""    )
      __SCREAMING_SNAKE_CASE      							=       self.dummy_vae
      __SCREAMING_SNAKE_CASE      							=       self.dummy_text_encoder
      __SCREAMING_SNAKE_CASE      							=       CLIPTokenizer.from_pretrained("""hf-internal-testing/tiny-random-clip"""    )

      __SCREAMING_SNAKE_CASE      							=       self.dummy_image.cpu().permute(0				,2				,3				,1    )[0]
      __SCREAMING_SNAKE_CASE      							=       Image.fromarray(np.uinta(lowerCamelCase    )    ).convert("""RGB"""    ).resize((64, 64)    )

      # put models in fp16, except vae as it overflows in fp16
      __SCREAMING_SNAKE_CASE      							=       unet.half()
      __SCREAMING_SNAKE_CASE      							=       text_encoder.half()

      # make sure here that pndm scheduler skips prk
      __SCREAMING_SNAKE_CASE      							=       StableDiffusionUpscalePipeline(
          unet=lowerCamelCase				,low_res_scheduler=lowerCamelCase				,scheduler=lowerCamelCase				,vae=lowerCamelCase				,text_encoder=lowerCamelCase				,tokenizer=lowerCamelCase				,max_noise_level=350				,)
      __SCREAMING_SNAKE_CASE      							=       sd_pipe.to(lowerCamelCase    )
      sd_pipe.set_progress_bar_config(disable=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       """A painting of a squirrel eating a burger"""
      __SCREAMING_SNAKE_CASE      							=       torch.manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       sd_pipe(
          [prompt]				,image=lowerCamelCase				,generator=lowerCamelCase				,num_inference_steps=2				,output_type="""np"""				,).images

      __SCREAMING_SNAKE_CASE      							=       low_res_image.size[0] * 4
      assert image.shape == (1, expected_height_width, expected_height_width, 3)







@slow
@require_torch_gpu
class __a(   unittest.TestCase			):





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      super().tearDown()
      gc.collect()
      torch.cuda.empty_cache()





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       load_image(
          """https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main"""
          """/sd2-upscale/low_res_cat.png"""    )
      __SCREAMING_SNAKE_CASE      							=       load_numpy(
          """https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/sd2-upscale"""
          """/upsampled_cat.npy"""    )

      __SCREAMING_SNAKE_CASE      							=       """stabilityai/stable-diffusion-x4-upscaler"""
      __SCREAMING_SNAKE_CASE      							=       StableDiffusionUpscalePipeline.from_pretrained(lowerCamelCase    )
      pipe.to(lowerCamelCase    )
      pipe.set_progress_bar_config(disable=lowerCamelCase    )
      pipe.enable_attention_slicing()

      __SCREAMING_SNAKE_CASE      							=       """a cat sitting on a park bench"""

      __SCREAMING_SNAKE_CASE      							=       torch.manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       pipe(
          prompt=lowerCamelCase				,image=lowerCamelCase				,generator=lowerCamelCase				,output_type="""np"""				,)
      __SCREAMING_SNAKE_CASE      							=       output.images[0]

      assert image.shape == (512, 512, 3)
      assert np.abs(expected_image - image    ).max() < 1E-3





   def      UpperCAmelCase__     (					self				:			Optional[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       load_image(
          """https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main"""
          """/sd2-upscale/low_res_cat.png"""    )
      __SCREAMING_SNAKE_CASE      							=       load_numpy(
          """https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/sd2-upscale"""
          """/upsampled_cat_fp16.npy"""    )

      __SCREAMING_SNAKE_CASE      							=       """stabilityai/stable-diffusion-x4-upscaler"""
      __SCREAMING_SNAKE_CASE      							=       StableDiffusionUpscalePipeline.from_pretrained(
          lowerCamelCase				,torch_dtype=torch.floataa				,)
      pipe.to(lowerCamelCase    )
      pipe.set_progress_bar_config(disable=lowerCamelCase    )
      pipe.enable_attention_slicing()

      __SCREAMING_SNAKE_CASE      							=       """a cat sitting on a park bench"""

      __SCREAMING_SNAKE_CASE      							=       torch.manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       pipe(
          prompt=lowerCamelCase				,image=lowerCamelCase				,generator=lowerCamelCase				,output_type="""np"""				,)
      __SCREAMING_SNAKE_CASE      							=       output.images[0]

      assert image.shape == (512, 512, 3)
      assert np.abs(expected_image - image    ).max() < 5E-1





   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      torch.cuda.empty_cache()
      torch.cuda.reset_max_memory_allocated()
      torch.cuda.reset_peak_memory_stats()

      __SCREAMING_SNAKE_CASE      							=       load_image(
          """https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main"""
          """/sd2-upscale/low_res_cat.png"""    )

      __SCREAMING_SNAKE_CASE      							=       """stabilityai/stable-diffusion-x4-upscaler"""
      __SCREAMING_SNAKE_CASE      							=       StableDiffusionUpscalePipeline.from_pretrained(
          lowerCamelCase				,torch_dtype=torch.floataa				,)
      pipe.to(lowerCamelCase    )
      pipe.set_progress_bar_config(disable=lowerCamelCase    )
      pipe.enable_attention_slicing(1    )
      pipe.enable_sequential_cpu_offload()

      __SCREAMING_SNAKE_CASE      							=       """a cat sitting on a park bench"""

      __SCREAMING_SNAKE_CASE      							=       torch.manual_seed(0    )
      __SCREAMING_SNAKE_CASE      							=       pipe(
          prompt=lowerCamelCase				,image=lowerCamelCase				,generator=lowerCamelCase				,num_inference_steps=5				,output_type="""np"""				,)

      __SCREAMING_SNAKE_CASE      							=       torch.cuda.max_memory_allocated()
      # make sure that less than 2.9 GB is allocated
      assert mem_bytes < 2.9 * 10**9












'''simple docstring'''

import sys
from collections import defaultdict







class __a :





   def __init__(					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       []





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			List[Any]    ):

      '''simple docstring'''

      return self.node_position[vertex]





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			str				,lowerCamelCase				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       pos





   def      UpperCAmelCase__     (					self				:			List[Any]				,lowerCamelCase				:			Optional[int]				,lowerCamelCase				:			Union[str, Any]				,lowerCamelCase				:			List[Any]				,lowerCamelCase				:			Any    ):

      '''simple docstring'''

      if start > size // 2 - 1:
         return
      else:
         if 2 * start + 2 >= size:
            __SCREAMING_SNAKE_CASE      							=       2 * start + 1
         else:
            if heap[2 * start + 1] < heap[2 * start + 2]:
               __SCREAMING_SNAKE_CASE      							=       2 * start + 1
            else:
               __SCREAMING_SNAKE_CASE      							=       2 * start + 2
         if heap[smallest_child] < heap[start]:
            __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       heap[smallest_child], positions[smallest_child]
            __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       (
                heap[start],
                positions[start],
            )
            __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       temp, tempa

            __SCREAMING_SNAKE_CASE      							=       self.get_position(positions[smallest_child]    )
            self.set_position(
                positions[smallest_child]				,self.get_position(positions[start]    )    )
            self.set_position(positions[start]				,lowerCamelCase    )

            self.top_to_bottom(lowerCamelCase				,lowerCamelCase				,lowerCamelCase				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Any				,lowerCamelCase				:			int				,lowerCamelCase				:			List[str]				,lowerCamelCase				:			Optional[Any]				,lowerCamelCase				:			Tuple    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       position[index]

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

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





   def      UpperCAmelCase__     (					self				:			Tuple				,lowerCamelCase				:			List[Any]				,lowerCamelCase				:			List[str]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       len(lowerCamelCase    ) // 2 - 1
      for i in range(lowerCamelCase				,-1				,-1    ):
         self.top_to_bottom(lowerCamelCase				,lowerCamelCase				,len(lowerCamelCase    )				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			int				,lowerCamelCase				:			Optional[int]				,lowerCamelCase				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       positions[0]
      __SCREAMING_SNAKE_CASE      							=       sys.maxsize
      self.top_to_bottom(lowerCamelCase				,0				,len(lowerCamelCase    )				,lowerCamelCase    )
      return temp





def 						__magic_name__       (							__UpperCAmelCase      )						->					Optional[Any]:

   '''simple docstring'''







   __SCREAMING_SNAKE_CASE      							=       Heap()

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

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

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

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


if __name__ == "__main__":  # pragma: no cover
    # < --------- Prims Algorithm --------- >
    a        =						int(input("Enter number of edges: ").strip())
    a        =						defaultdict(list)
    for _ in range(edges_number):
        a        =						[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))





