






import gc
import unittest

import numpy as np
import torch
import torch.nn.functional as F
from transformers import (
    ClapTextConfig,
    ClapTextModelWithProjection,
    RobertaTokenizer,
    SpeechTaHifiGan,
    SpeechTaHifiGanConfig,
)

from diffusers import (
    AudioLDMPipeline,
    AutoencoderKL,
    DDIMScheduler,
    LMSDiscreteScheduler,
    PNDMScheduler,
    UNetaDConditionModel,
)
from diffusers.utils import is_xformers_available, slow, torch_device
from diffusers.utils.testing_utils import enable_full_determinism

from ..pipeline_params import TEXT_TO_AUDIO_BATCH_PARAMS, TEXT_TO_AUDIO_PARAMS
from ..test_pipelines_common import PipelineTesterMixin


enable_full_determinism()
class        a       (					lowercase__				,			unittest.TestCase  ):



      """simple docstring"""


      a    :					List[Any]							=      AudioLDMPipeline
      a    :					Optional[Any]							=      TEXT_TO_AUDIO_PARAMS
      a    :					Dict							=      TEXT_TO_AUDIO_BATCH_PARAMS
      a    :					Optional[int]							=      frozenset(
          [
              'num_inference_steps',
              'num_waveforms_per_prompt',
              'generator',
              'latents',
              'output_type',
              'return_dict',
              'callback',
              'callback_steps',
          ]  )
      def       UpperCAmelCase ( self   :     Any   )				-> List[str]:
        torch.manual_seed(0   )
        __UpperCAmelCase				:      List[Any]	 =    UNetaDConditionModel(
            block_out_channels=(32, 64)						, layers_per_block=2						, sample_size=32						, in_channels=4						, out_channels=4						, down_block_types=("""DownBlock2D""", """CrossAttnDownBlock2D""")						, up_block_types=("""CrossAttnUpBlock2D""", """UpBlock2D""")						, cross_attention_dim=(32, 64)						, class_embed_type="""simple_projection"""						, projection_class_embeddings_input_dim=32						, class_embeddings_concat=__lowercase						, )
        __UpperCAmelCase				:      Optional[int]	 =    DDIMScheduler(
            beta_start=0.00_085						, beta_end=0.012						, beta_schedule="""scaled_linear"""						, clip_sample=__lowercase						, set_alpha_to_one=__lowercase						, )
        torch.manual_seed(0   )
        __UpperCAmelCase				:      Optional[Any]	 =    AutoencoderKL(
            block_out_channels=[32, 64]						, in_channels=1						, out_channels=1						, down_block_types=["""DownEncoderBlock2D""", """DownEncoderBlock2D"""]						, up_block_types=["""UpDecoderBlock2D""", """UpDecoderBlock2D"""]						, latent_channels=4						, )
        torch.manual_seed(0   )
        __UpperCAmelCase				:      Optional[Any]	 =    ClapTextConfig(
            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						, projection_dim=32						, )
        __UpperCAmelCase				:      Optional[int]	 =    ClapTextModelWithProjection(__lowercase   )
        __UpperCAmelCase				:      str	 =    RobertaTokenizer.from_pretrained("""hf-internal-testing/tiny-random-roberta"""						, model_max_length=77   )

        __UpperCAmelCase				:      Dict	 =    SpeechTaHifiGanConfig(
            model_in_dim=8						, sampling_rate=16000						, upsample_initial_channel=16						, upsample_rates=[2, 2]						, upsample_kernel_sizes=[4, 4]						, resblock_kernel_sizes=[3, 7]						, resblock_dilation_sizes=[[1, 3, 5], [1, 3, 5]]						, normalize_before=__lowercase						, )

        __UpperCAmelCase				:      int	 =    SpeechTaHifiGan(__lowercase   )

        __UpperCAmelCase				:      Tuple	 =    {
            """unet""": unet,
            """scheduler""": scheduler,
            """vae""": vae,
            """text_encoder""": text_encoder,
            """tokenizer""": tokenizer,
            """vocoder""": vocoder,
        }
        return components
      def       UpperCAmelCase ( self   :     Optional[int]						, __lowercase   :     Any						, __lowercase   :     str=0   )				-> List[str]:
        if str(__lowercase   ).startswith("""mps"""   ):
          __UpperCAmelCase				:      Dict	 =    torch.manual_seed(__lowercase   )
        else:
          __UpperCAmelCase				:      Tuple	 =    torch.Generator(device=__lowercase   ).manual_seed(__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    {
            """prompt""": """A hammer hitting a wooden surface""",
            """generator""": generator,
            """num_inference_steps""": 2,
            """guidance_scale""": 6.0,
        }
        return inputs
      def       UpperCAmelCase ( self   :     Tuple   )				-> Union[str, Any]:
        __UpperCAmelCase				:      Tuple	 =    """cpu"""  # ensure determinism for the device-dependent torch.Generator

        __UpperCAmelCase				:      Dict	 =    self.get_dummy_components()
        __UpperCAmelCase				:      List[Any]	 =    AudioLDMPipeline(**__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      List[Any]	 =    self.get_dummy_inputs(__lowercase   )
        __UpperCAmelCase				:      Union[str, Any]	 =    audioldm_pipe(**__lowercase   )
        __UpperCAmelCase				:      Union[str, Any]	 =    output.audios[0]

        assert audio.ndim == 1
        assert len(__lowercase   ) == 256

        __UpperCAmelCase				:      str	 =    audio[:10]
        __UpperCAmelCase				:      List[Any]	 =    np.array(
            [-0.0_050, 0.0_050, -0.0_060, 0.0_033, -0.0_026, 0.0_033, -0.0_027, 0.0_033, -0.0_028, 0.0_033]   )

        assert np.abs(audio_slice - expected_slice   ).max() < 1e-2
      def       UpperCAmelCase ( self   :     Tuple   )				-> Optional[int]:
        __UpperCAmelCase				:      List[str]	 =    self.get_dummy_components()
        __UpperCAmelCase				:      Any	 =    AudioLDMPipeline(**__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    audioldm_pipe.to(__lowercase   )
        __UpperCAmelCase				:      str	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      Tuple	 =    self.get_dummy_inputs(__lowercase   )
        __UpperCAmelCase				:      Dict	 =    3 * [inputs["""prompt"""]]

        # forward
        __UpperCAmelCase				:      Union[str, Any]	 =    audioldm_pipe(**__lowercase   )
        __UpperCAmelCase				:      int	 =    output.audios[0]

        __UpperCAmelCase				:      List[str]	 =    self.get_dummy_inputs(__lowercase   )
        __UpperCAmelCase				:      Any	 =    3 * [inputs.pop("""prompt"""   )]

        __UpperCAmelCase				:      Tuple	 =    audioldm_pipe.tokenizer(
            __lowercase						, padding="""max_length"""						, max_length=audioldm_pipe.tokenizer.model_max_length						, truncation=__lowercase						, return_tensors="""pt"""						, )
        __UpperCAmelCase				:      Optional[Any]	 =    text_inputs["""input_ids"""].to(__lowercase   )

        __UpperCAmelCase				:      int	 =    audioldm_pipe.text_encoder(
            __lowercase						, )
        __UpperCAmelCase				:      Dict	 =    prompt_embeds.text_embeds
        # additional L_2 normalization over each hidden-state
        __UpperCAmelCase				:      Tuple	 =    F.normalize(__lowercase						, dim=-1   )

        __UpperCAmelCase				:      Tuple	 =    prompt_embeds

        # forward
        __UpperCAmelCase				:      Dict	 =    audioldm_pipe(**__lowercase   )
        __UpperCAmelCase				:      str	 =    output.audios[0]

        assert np.abs(audio_a - audio_a   ).max() < 1e-2
      def       UpperCAmelCase ( self   :     Union[str, Any]   )				-> str:
        __UpperCAmelCase				:      Tuple	 =    self.get_dummy_components()
        __UpperCAmelCase				:      Any	 =    AudioLDMPipeline(**__lowercase   )
        __UpperCAmelCase				:      Dict	 =    audioldm_pipe.to(__lowercase   )
        __UpperCAmelCase				:      int	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      Union[str, Any]	 =    self.get_dummy_inputs(__lowercase   )
        __UpperCAmelCase				:      Optional[Any]	 =    3 * ["""this is a negative prompt"""]
        __UpperCAmelCase				:      Optional[Any]	 =    negative_prompt
        __UpperCAmelCase				:      Tuple	 =    3 * [inputs["""prompt"""]]

        # forward
        __UpperCAmelCase				:      int	 =    audioldm_pipe(**__lowercase   )
        __UpperCAmelCase				:      Any	 =    output.audios[0]

        __UpperCAmelCase				:      List[Any]	 =    self.get_dummy_inputs(__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    3 * [inputs.pop("""prompt"""   )]

        __UpperCAmelCase				:      List[Any]	 =    []
        for p in [prompt, negative_prompt]:
          __UpperCAmelCase				:      List[str]	 =    audioldm_pipe.tokenizer(
              __lowercase						, padding="""max_length"""						, max_length=audioldm_pipe.tokenizer.model_max_length						, truncation=__lowercase						, return_tensors="""pt"""						, )
          __UpperCAmelCase				:      Union[str, Any]	 =    text_inputs["""input_ids"""].to(__lowercase   )

          __UpperCAmelCase				:      Optional[Any]	 =    audioldm_pipe.text_encoder(
              __lowercase						, )
          __UpperCAmelCase				:      Tuple	 =    text_embeds.text_embeds
          # additional L_2 normalization over each hidden-state
          __UpperCAmelCase				:      Any	 =    F.normalize(__lowercase						, dim=-1   )

          embeds.append(__lowercase   )

        __UpperCAmelCase ,					__UpperCAmelCase				:      Optional[int]	 =    embeds

        # forward
        __UpperCAmelCase				:      str	 =    audioldm_pipe(**__lowercase   )
        __UpperCAmelCase				:      str	 =    output.audios[0]

        assert np.abs(audio_a - audio_a   ).max() < 1e-2
      def       UpperCAmelCase ( self   :     Dict   )				-> Tuple:
        __UpperCAmelCase				:      str	 =    """cpu"""  # ensure determinism for the device-dependent torch.Generator
        __UpperCAmelCase				:      List[Any]	 =    self.get_dummy_components()
        __UpperCAmelCase				:      Union[str, Any]	 =    PNDMScheduler(skip_prk_steps=__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    AudioLDMPipeline(**__lowercase   )
        __UpperCAmelCase				:      str	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      Union[str, Any]	 =    self.get_dummy_inputs(__lowercase   )
        __UpperCAmelCase				:      Optional[Any]	 =    """egg cracking"""
        __UpperCAmelCase				:      Optional[Any]	 =    audioldm_pipe(**__lowercase						, negative_prompt=__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    output.audios[0]

        assert audio.ndim == 1
        assert len(__lowercase   ) == 256

        __UpperCAmelCase				:      Union[str, Any]	 =    audio[:10]
        __UpperCAmelCase				:      int	 =    np.array(
            [-0.0_051, 0.0_050, -0.0_060, 0.0_034, -0.0_026, 0.0_033, -0.0_027, 0.0_033, -0.0_028, 0.0_032]   )

        assert np.abs(audio_slice - expected_slice   ).max() < 1e-2
      def       UpperCAmelCase ( self   :     str   )				-> Any:
        __UpperCAmelCase				:      str	 =    """cpu"""  # ensure determinism for the device-dependent torch.Generator
        __UpperCAmelCase				:      List[Any]	 =    self.get_dummy_components()
        __UpperCAmelCase				:      str	 =    PNDMScheduler(skip_prk_steps=__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    AudioLDMPipeline(**__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      str	 =    """A hammer hitting a wooden surface"""

        # test num_waveforms_per_prompt=1 (default)
        __UpperCAmelCase				:      Union[str, Any]	 =    audioldm_pipe(__lowercase						, num_inference_steps=2   ).audios

        assert audios.shape == (1, 256)

        # test num_waveforms_per_prompt=1 (default) for batch of prompts
        __UpperCAmelCase				:      Optional[Any]	 =    2
        __UpperCAmelCase				:      int	 =    audioldm_pipe([prompt] * batch_size						, num_inference_steps=2   ).audios

        assert audios.shape == (batch_size, 256)

        # test num_waveforms_per_prompt for single prompt
        __UpperCAmelCase				:      int	 =    2
        __UpperCAmelCase				:      str	 =    audioldm_pipe(__lowercase						, num_inference_steps=2						, num_waveforms_per_prompt=__lowercase   ).audios

        assert audios.shape == (num_waveforms_per_prompt, 256)

        # test num_waveforms_per_prompt for batch of prompts
        __UpperCAmelCase				:      Any	 =    2
        __UpperCAmelCase				:      Tuple	 =    audioldm_pipe(
            [prompt] * batch_size						, num_inference_steps=2						, num_waveforms_per_prompt=__lowercase   ).audios

        assert audios.shape == (batch_size * num_waveforms_per_prompt, 256)
      def       UpperCAmelCase ( self   :     List[str]   )				-> str:
        __UpperCAmelCase				:      Optional[Any]	 =    """cpu"""  # ensure determinism for the device-dependent torch.Generator
        __UpperCAmelCase				:      Tuple	 =    self.get_dummy_components()
        __UpperCAmelCase				:      int	 =    AudioLDMPipeline(**__lowercase   )
        __UpperCAmelCase				:      Dict	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )
        __UpperCAmelCase				:      List[str]	 =    audioldm_pipe.vocoder.config.sampling_rate

        __UpperCAmelCase				:      Union[str, Any]	 =    self.get_dummy_inputs(__lowercase   )
        __UpperCAmelCase				:      Optional[Any]	 =    audioldm_pipe(audio_length_in_s=0.016						, **__lowercase   )
        __UpperCAmelCase				:      Tuple	 =    output.audios[0]

        assert audio.ndim == 1
        assert len(__lowercase   ) / vocoder_sampling_rate == 0.016

        __UpperCAmelCase				:      Optional[Any]	 =    audioldm_pipe(audio_length_in_s=0.032						, **__lowercase   )
        __UpperCAmelCase				:      Dict	 =    output.audios[0]

        assert audio.ndim == 1
        assert len(__lowercase   ) / vocoder_sampling_rate == 0.032
      def       UpperCAmelCase ( self   :     Any   )				-> List[Any]:
        __UpperCAmelCase				:      List[Any]	 =    self.get_dummy_components()
        __UpperCAmelCase				:      Any	 =    AudioLDMPipeline(**__lowercase   )
        __UpperCAmelCase				:      Dict	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      List[str]	 =    ["""hey"""]

        __UpperCAmelCase				:      Dict	 =    audioldm_pipe(__lowercase						, num_inference_steps=1   )
        __UpperCAmelCase				:      Tuple	 =    output.audios.shape
        assert audio_shape == (1, 256)

        __UpperCAmelCase				:      Optional[Any]	 =    audioldm_pipe.vocoder.config
        config.model_in_dim *= 2
        __UpperCAmelCase				:      List[Any]	 =    SpeechTaHifiGan(__lowercase   ).to(__lowercase   )
        __UpperCAmelCase				:      Dict	 =    audioldm_pipe(__lowercase						, num_inference_steps=1   )
        __UpperCAmelCase				:      int	 =    output.audios.shape
        # waveform shape is unchanged, we just have 2x the number of mel channels in the spectrogram
        assert audio_shape == (1, 256)
      def       UpperCAmelCase ( self   :     Dict   )				-> Optional[int]:
        self._test_attention_slicing_forward_pass(test_mean_pixel_difference=__lowercase   )
      def       UpperCAmelCase ( self   :     str   )				-> Any:
        self._test_inference_batch_single_identical(test_mean_pixel_difference=__lowercase   )




      @unittest.skipIf(
          torch_device != """cuda""" or not is_xformers_available()						, reason="""XFormers attention is only available with CUDA and `xformers` installed"""						, )
      def       UpperCAmelCase ( self   :     Optional[Any]   )				-> Optional[Any]:
        self._test_xformers_attention_forwardGenerator_pass(test_mean_pixel_difference=__lowercase   )


@slow
class        a       (					unittest.TestCase  ):



      """simple docstring"""


      def       UpperCAmelCase ( self   :     Dict   )				-> Tuple:
        super().tearDown()
        gc.collect()
        torch.cuda.empty_cache()
      def       UpperCAmelCase ( self   :     Optional[Any]						, __lowercase   :     Optional[int]						, __lowercase   :     int="cpu"						, __lowercase   :     List[Any]=torch.floataa						, __lowercase   :     Tuple=0   )				-> Dict:
        __UpperCAmelCase				:      int	 =    torch.Generator(device=__lowercase   ).manual_seed(__lowercase   )
        __UpperCAmelCase				:      Dict	 =    np.random.RandomState(__lowercase   ).standard_normal((1, 8, 128, 16)   )
        __UpperCAmelCase				:      Optional[Any]	 =    torch.from_numpy(__lowercase   ).to(device=__lowercase						, dtype=__lowercase   )
        __UpperCAmelCase				:      int	 =    {
            """prompt""": """A hammer hitting a wooden surface""",
            """latents""": latents,
            """generator""": generator,
            """num_inference_steps""": 3,
            """guidance_scale""": 2.5,
        }
        return inputs
      def       UpperCAmelCase ( self   :     int   )				-> List[str]:
        __UpperCAmelCase				:      Any	 =    AudioLDMPipeline.from_pretrained("""cvssp/audioldm"""   )
        __UpperCAmelCase				:      Union[str, Any]	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      Tuple	 =    self.get_inputs(__lowercase   )
        __UpperCAmelCase				:      str	 =    25
        __UpperCAmelCase				:      Optional[int]	 =    audioldm_pipe(**__lowercase   ).audios[0]

        assert audio.ndim == 1
        assert len(__lowercase   ) == 81920

        __UpperCAmelCase				:      Dict	 =    audio[77230:77240]
        __UpperCAmelCase				:      Optional[Any]	 =    np.array(
            [-0.4_884, -0.4_607, 0.0_023, 0.5_007, 0.5_896, 0.5_151, 0.3_813, -0.0_208, -0.3_687, -0.4_315]   )
        __UpperCAmelCase				:      Optional[Any]	 =    np.abs(expected_slice - audio_slice   ).max()
        assert max_diff < 1e-2




      def       UpperCAmelCase ( self   :     str   )				-> Tuple:
        __UpperCAmelCase				:      Optional[Any]	 =    AudioLDMPipeline.from_pretrained("""cvssp/audioldm"""   )
        __UpperCAmelCase				:      Any	 =    LMSDiscreteScheduler.from_config(audioldm_pipe.scheduler.config   )
        __UpperCAmelCase				:      int	 =    audioldm_pipe.to(__lowercase   )
        audioldm_pipe.set_progress_bar_config(disable=__lowercase   )

        __UpperCAmelCase				:      List[Any]	 =    self.get_inputs(__lowercase   )
        __UpperCAmelCase				:      Optional[int]	 =    audioldm_pipe(**__lowercase   ).audios[0]

        assert audio.ndim == 1
        assert len(__lowercase   ) == 81920

        __UpperCAmelCase				:      int	 =    audio[27780:27790]
        __UpperCAmelCase				:      Optional[Any]	 =    np.array([-0.2_131, -0.0_873, -0.0_124, -0.0_189, 0.0_569, 0.1_373, 0.1_883, 0.2_886, 0.3_297, 0.2_212]   )
        __UpperCAmelCase				:      Dict	 =    np.abs(expected_slice - audio_slice   ).max()
        assert max_diff < 3e-2



import sys
from collections import defaultdict
class     lowerCAmelCase_     :







							def __init__(   self      :     Optional[int]		):
												_UpperCamelCase			     =     []







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     str		):
												return self.node_position[vertex]







							def  UpperCamelCase_						(   self      :     Optional[Any] ,			_A      :     List[str] ,			_A      :     Union[str, Any]		):
												_UpperCamelCase			     =     pos







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     List[str] ,			_A      :     int ,			_A      :     Optional[Any] ,			_A      :     Union[str, Any]		):
												if start > size // 2 - 1:
																	return
												else:
																	if 2 * start + 2 >= size:
																						_UpperCamelCase			     =     2 * start + 1
																	else:
																						if heap[2 * start + 1] < heap[2 * start + 2]:
																											_UpperCamelCase			     =     2 * start + 1
																						else:
																											_UpperCamelCase			     =     2 * start + 2
																	if heap[smallest_child] < heap[start]:
																						_UpperCamelCase     ,    _UpperCamelCase			     =     heap[smallest_child], positions[smallest_child]
																						_UpperCamelCase     ,    _UpperCamelCase			     =     (
																						    heap[start],
																						    positions[start],
																						)
																						_UpperCamelCase     ,    _UpperCamelCase			     =     temp, tempa

																						_UpperCamelCase			     =     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  UpperCamelCase_						(   self      :     List[str] ,			_A      :     Tuple ,			_A      :     Optional[Any] ,			_A      :     int ,			_A      :     Optional[int]		):
												_UpperCamelCase			     =     position[index]

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

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







							def  UpperCamelCase_						(   self      :     int ,			_A      :     Tuple ,			_A      :     int		):
												_UpperCamelCase			     =     len(_A		) // 2 - 1
												for i in range(_A ,			-1 ,			-1		):
																	self.top_to_bottom(_A ,			_A ,			len(_A		) ,			_A		)







							def  UpperCamelCase_						(   self      :     Any ,			_A      :     int ,			_A      :     List[str]		):
												_UpperCamelCase			     =     positions[0]
												_UpperCamelCase			     =     sys.maxsize
												self.top_to_bottom(_A ,			0 ,			len(_A		) ,			_A		)
												return temp




def 					_snake_case	(  __snake_case						):
					_UpperCamelCase			     =     Heap()

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

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

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

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


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