





'''simple docstring'''

import inspect
import unittest

from huggingface_hub import hf_hub_download

from transformers import ASTConfig
from transformers.testing_utils import require_torch, require_torchaudio, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_torchaudio_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
    import torch
    from torch import nn

    from transformers import ASTForAudioClassification, ASTModel
    from transformers.models.audio_spectrogram_transformer.modeling_audio_spectrogram_transformer import (
        AUDIO_SPECTROGRAM_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
    )


if is_torchaudio_available():
    import torchaudio

    from transformers import ASTFeatureExtractor







class __a:





   def __init__(					self				:			Optional[int]				,lowerCamelCase				:			Union[str, Any]				,lowerCamelCase				:			List[str]=13				,lowerCamelCase				:			List[Any]=2				,lowerCamelCase				:			Optional[Any]=24				,lowerCamelCase				:			Any=16				,lowerCamelCase				:			int=True				,lowerCamelCase				:			List[Any]=True				,lowerCamelCase				:			Union[str, Any]=32				,lowerCamelCase				:			int=5				,lowerCamelCase				:			Union[str, Any]=4				,lowerCamelCase				:			Optional[int]=37				,lowerCamelCase				:			Any="gelu"				,lowerCamelCase				:			Union[str, Any]=0.1				,lowerCamelCase				:			int=0.1				,lowerCamelCase				:			Union[str, Any]=10				,lowerCamelCase				:			List[str]=0.02				,lowerCamelCase				:			Union[str, Any]=None				,lowerCamelCase				:			int=2				,lowerCamelCase				:			Optional[Any]=2				,):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       parent
      __SCREAMING_SNAKE_CASE      							=       batch_size
      __SCREAMING_SNAKE_CASE      							=       patch_size
      __SCREAMING_SNAKE_CASE      							=       max_length
      __SCREAMING_SNAKE_CASE      							=       num_mel_bins
      __SCREAMING_SNAKE_CASE      							=       is_training
      __SCREAMING_SNAKE_CASE      							=       use_labels
      __SCREAMING_SNAKE_CASE      							=       hidden_size
      __SCREAMING_SNAKE_CASE      							=       num_hidden_layers
      __SCREAMING_SNAKE_CASE      							=       num_attention_heads
      __SCREAMING_SNAKE_CASE      							=       intermediate_size
      __SCREAMING_SNAKE_CASE      							=       hidden_act
      __SCREAMING_SNAKE_CASE      							=       hidden_dropout_prob
      __SCREAMING_SNAKE_CASE      							=       attention_probs_dropout_prob
      __SCREAMING_SNAKE_CASE      							=       type_sequence_label_size
      __SCREAMING_SNAKE_CASE      							=       initializer_range
      __SCREAMING_SNAKE_CASE      							=       scope
      __SCREAMING_SNAKE_CASE      							=       frequency_stride
      __SCREAMING_SNAKE_CASE      							=       time_stride

      # in AST, the seq length equals the number of patches + 2 (we add 2 for the [CLS] and distillation tokens)
      __SCREAMING_SNAKE_CASE      							=       (self.num_mel_bins - self.patch_size) // self.frequency_stride + 1
      __SCREAMING_SNAKE_CASE      							=       (self.max_length - self.patch_size) // self.time_stride + 1
      __SCREAMING_SNAKE_CASE      							=       frequency_out_dimension * time_out_dimension
      __SCREAMING_SNAKE_CASE      							=       num_patches + 2





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       floats_tensor([self.batch_size, self.max_length, self.num_mel_bins]    )

      __SCREAMING_SNAKE_CASE      							=       None
      if self.use_labels:
         __SCREAMING_SNAKE_CASE      							=       ids_tensor([self.batch_size]				,self.type_sequence_label_size    )

      __SCREAMING_SNAKE_CASE      							=       self.get_config()

      return config, input_values, labels





   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      return ASTConfig(
          patch_size=self.patch_size				,max_length=self.max_length				,num_mel_bins=self.num_mel_bins				,hidden_size=self.hidden_size				,num_hidden_layers=self.num_hidden_layers				,num_attention_heads=self.num_attention_heads				,intermediate_size=self.intermediate_size				,hidden_act=self.hidden_act				,hidden_dropout_prob=self.hidden_dropout_prob				,attention_probs_dropout_prob=self.attention_probs_dropout_prob				,is_decoder=__UpperCamelCase				,initializer_range=self.initializer_range				,frequency_stride=self.frequency_stride				,time_stride=self.time_stride				,)





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       ASTModel(config=__UpperCamelCase    )
      model.to(__UpperCamelCase    )
      model.eval()
      __SCREAMING_SNAKE_CASE      							=       model(__UpperCamelCase    )
      self.parent.assertEqual(result.last_hidden_state.shape				,(self.batch_size, self.seq_length, self.hidden_size)    )





   def      UpperCAmelCase__     (					self				:			str    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.prepare_config_and_inputs()
      (
          (
          __SCREAMING_SNAKE_CASE       
      )							,     (
          __SCREAMING_SNAKE_CASE       
      )							,     (
          __SCREAMING_SNAKE_CASE       
      )							,            
      )      							=       config_and_inputs
      __SCREAMING_SNAKE_CASE      							=       {"""input_values""": input_values}
      return config, inputs_dict







@require_torch
class __a(   __snake_case,   __snake_case,   unittest.TestCase			):
   __UpperCamelCase   : Optional[Any]	      =	(
       (
           ASTModel,
           ASTForAudioClassification,
       )
       if is_torch_available()
       else ()
   )
   __UpperCamelCase   : List[Any]	      =	(
       {'audio-classification': ASTForAudioClassification, 'feature-extraction': ASTModel}
       if is_torch_available()
       else {}
   )
   __UpperCamelCase   : Optional[int]	      =	False
   __UpperCamelCase   : List[Any]	      =	False
   __UpperCamelCase   : List[str]	      =	False
   __UpperCamelCase   : List[Any]	      =	False





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

      '''simple docstring'''

      if pipeline_test_casse_name == "AudioClassificationPipelineTests":
         return True

      return False





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       ASTModelTester(self    )
      __SCREAMING_SNAKE_CASE      							=       ConfigTester(self				,config_class=__UpperCamelCase				,has_text_modality=__UpperCamelCase				,hidden_size=37    )





   def      UpperCAmelCase__     (					self				:			List[str]    ):

      '''simple docstring'''

      self.config_tester.run_common_tests()





   @unittest.skip(reason="""AST does not use inputs_embeds"""    )
   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      pass





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs_for_common()

      for model_class in self.all_model_classes:
         __SCREAMING_SNAKE_CASE      							=       model_class(__UpperCamelCase    )
         self.assertIsInstance(model.get_input_embeddings()				,(nn.Module)    )
         __SCREAMING_SNAKE_CASE      							=       model.get_output_embeddings()
         self.assertTrue(x is None or isinstance(__UpperCamelCase				,nn.Linear    )    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs_for_common()

      for model_class in self.all_model_classes:
         __SCREAMING_SNAKE_CASE      							=       model_class(__UpperCamelCase    )
         __SCREAMING_SNAKE_CASE      							=       inspect.signature(model.forward    )
         # signature.parameters is an OrderedDict => so arg_names order is deterministic
         __SCREAMING_SNAKE_CASE      							=       [*signature.parameters.keys()]

         __SCREAMING_SNAKE_CASE      							=       ["""input_values"""]
         self.assertListEqual(arg_names[:1]				,__UpperCamelCase    )





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_model(*__UpperCamelCase    )





   @slow
   def      UpperCAmelCase__     (					self				:			List[str]    ):

      '''simple docstring'''

      for model_name in AUDIO_SPECTROGRAM_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
         __SCREAMING_SNAKE_CASE      							=       ASTModel.from_pretrained(__UpperCamelCase    )
         self.assertIsNotNone(__UpperCamelCase    )





def 						__magic_name__       (							)						->					Union[str, Any]:

   '''simple docstring'''







   __SCREAMING_SNAKE_CASE      							=       hf_hub_download(
       repo_id="""nielsr/audio-spectogram-transformer-checkpoint"""							,	filename="""sample_audio.flac"""							,	repo_type="""dataset"""      )

   __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       torchaudio.load(lowercase__      )

   return audio, sampling_rate







@require_torch
@require_torchaudio
class __a(   unittest.TestCase			):





   @cached_property
   def      UpperCAmelCase__     (					self				:			int    ):

      '''simple docstring'''

      return (
          ASTFeatureExtractor.from_pretrained("""MIT/ast-finetuned-audioset-10-10-0.4593"""    )
          if is_torchaudio_available()
          else None
      )





   @slow
   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.default_feature_extractor
      __SCREAMING_SNAKE_CASE      							=       ASTForAudioClassification.from_pretrained("""MIT/ast-finetuned-audioset-10-10-0.4593"""    ).to(__UpperCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       self.default_feature_extractor
      __SCREAMING_SNAKE_CASE							,     __SCREAMING_SNAKE_CASE      							=       prepare_audio()
      __SCREAMING_SNAKE_CASE      							=       audio.squeeze().numpy()
      __SCREAMING_SNAKE_CASE      							=       feature_extractor(__UpperCamelCase				,sampling_rate=__UpperCamelCase				,return_tensors="""pt"""    ).to(__UpperCamelCase    )

      # forward pass
      with torch.no_grad():
         __SCREAMING_SNAKE_CASE      							=       model(**__UpperCamelCase    )

      # verify the logits
      __SCREAMING_SNAKE_CASE      							=       torch.Size((1, 527)    )
      self.assertEqual(outputs.logits.shape				,__UpperCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       torch.tensor([-0.8_760, -7.0_042, -8.6_602]    ).to(__UpperCamelCase    )

      self.assertTrue(torch.allclose(outputs.logits[0, :3]				,__UpperCamelCase				,atol=1E-4    )    )












'''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))





