





'''simple docstring'''

from __future__ import annotations

import unittest

from transformers import RoFormerConfig, is_tf_available
from transformers.testing_utils import require_tf, slow

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
    import tensorflow as tf

    from transformers import (
        TFRoFormerForCausalLM,
        TFRoFormerForMaskedLM,
        TFRoFormerForMultipleChoice,
        TFRoFormerForQuestionAnswering,
        TFRoFormerForSequenceClassification,
        TFRoFormerForTokenClassification,
        TFRoFormerModel,
    )
    from transformers.models.roformer.modeling_tf_roformer import (
        TFRoFormerSelfAttention,
        TFRoFormerSinusoidalPositionalEmbedding,
    )







class __a:





   def __init__(					self				:			Union[str, Any]				,lowerCamelCase				:			Dict				,lowerCamelCase				:			str=13				,lowerCamelCase				:			Optional[Any]=7				,lowerCamelCase				:			Tuple=True				,lowerCamelCase				:			Any=True				,lowerCamelCase				:			Optional[int]=True				,lowerCamelCase				:			Optional[int]=True				,lowerCamelCase				:			Optional[int]=99				,lowerCamelCase				:			Union[str, Any]=32				,lowerCamelCase				:			str=2				,lowerCamelCase				:			List[Any]=4				,lowerCamelCase				:			List[Any]=37				,lowerCamelCase				:			str="gelu"				,lowerCamelCase				:			Union[str, Any]=0.1				,lowerCamelCase				:			str=0.1				,lowerCamelCase				:			Optional[int]=512				,lowerCamelCase				:			List[Any]=16				,lowerCamelCase				:			Optional[int]=2				,lowerCamelCase				:			Dict=0.02				,lowerCamelCase				:			int=3				,lowerCamelCase				:			List[Any]=4				,lowerCamelCase				:			int=None				,):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       parent
      __SCREAMING_SNAKE_CASE      							=       13
      __SCREAMING_SNAKE_CASE      							=       7
      __SCREAMING_SNAKE_CASE      							=       True
      __SCREAMING_SNAKE_CASE      							=       True
      __SCREAMING_SNAKE_CASE      							=       True
      __SCREAMING_SNAKE_CASE      							=       True
      __SCREAMING_SNAKE_CASE      							=       99
      __SCREAMING_SNAKE_CASE      							=       32
      __SCREAMING_SNAKE_CASE      							=       2
      __SCREAMING_SNAKE_CASE      							=       4
      __SCREAMING_SNAKE_CASE      							=       37
      __SCREAMING_SNAKE_CASE      							=       '''gelu'''
      __SCREAMING_SNAKE_CASE      							=       0.1
      __SCREAMING_SNAKE_CASE      							=       0.1
      __SCREAMING_SNAKE_CASE      							=       512
      __SCREAMING_SNAKE_CASE      							=       16
      __SCREAMING_SNAKE_CASE      							=       2
      __SCREAMING_SNAKE_CASE      							=       0.02
      __SCREAMING_SNAKE_CASE      							=       3
      __SCREAMING_SNAKE_CASE      							=       4
      __SCREAMING_SNAKE_CASE      							=       None





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       ids_tensor([self.batch_size, self.seq_length]				,self.vocab_size    )

      __SCREAMING_SNAKE_CASE      							=       None
      if self.use_input_mask:
         __SCREAMING_SNAKE_CASE      							=       random_attention_mask([self.batch_size, self.seq_length]    )

      __SCREAMING_SNAKE_CASE      							=       None
      if self.use_token_type_ids:
         __SCREAMING_SNAKE_CASE      							=       ids_tensor([self.batch_size, self.seq_length]				,self.type_vocab_size    )

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

      __SCREAMING_SNAKE_CASE      							=       RoFormerConfig(
          vocab_size=self.vocab_size				,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				,max_position_embeddings=self.max_position_embeddings				,type_vocab_size=self.type_vocab_size				,initializer_range=self.initializer_range				,return_dict=__lowerCamelCase				,)

      return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerModel(config=__lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       {'''input_ids''': input_ids, '''attention_mask''': input_mask, '''token_type_ids''': token_type_ids}

      __SCREAMING_SNAKE_CASE      							=       [input_ids, input_mask]
      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )

      self.parent.assertEqual(result.last_hidden_state.shape				,(self.batch_size, self.seq_length, self.hidden_size)    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       True
      __SCREAMING_SNAKE_CASE      							=       TFRoFormerForCausalLM(config=__lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       {
          '''input_ids''': input_ids,
          '''attention_mask''': input_mask,
          '''token_type_ids''': token_type_ids,
      }
      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )['''logits''']
      self.parent.assertListEqual(
          list(prediction_scores.numpy().shape    )				,[self.batch_size, self.seq_length, self.vocab_size]    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerForMaskedLM(config=__lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       {
          '''input_ids''': input_ids,
          '''attention_mask''': input_mask,
          '''token_type_ids''': token_type_ids,
      }
      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )
      self.parent.assertEqual(result.logits.shape				,(self.batch_size, self.seq_length, self.vocab_size)    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.num_labels
      __SCREAMING_SNAKE_CASE      							=       TFRoFormerForSequenceClassification(config=__lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       {
          '''input_ids''': input_ids,
          '''attention_mask''': input_mask,
          '''token_type_ids''': token_type_ids,
      }

      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )
      self.parent.assertEqual(result.logits.shape				,(self.batch_size, self.num_labels)    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.num_choices
      __SCREAMING_SNAKE_CASE      							=       TFRoFormerForMultipleChoice(config=__lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       tf.tile(tf.expand_dims(__lowerCamelCase				,1    )				,(1, self.num_choices, 1)    )
      __SCREAMING_SNAKE_CASE      							=       tf.tile(tf.expand_dims(__lowerCamelCase				,1    )				,(1, self.num_choices, 1)    )
      __SCREAMING_SNAKE_CASE      							=       tf.tile(tf.expand_dims(__lowerCamelCase				,1    )				,(1, self.num_choices, 1)    )
      __SCREAMING_SNAKE_CASE      							=       {
          '''input_ids''': multiple_choice_inputs_ids,
          '''attention_mask''': multiple_choice_input_mask,
          '''token_type_ids''': multiple_choice_token_type_ids,
      }
      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )
      self.parent.assertEqual(result.logits.shape				,(self.batch_size, self.num_choices)    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.num_labels
      __SCREAMING_SNAKE_CASE      							=       TFRoFormerForTokenClassification(config=__lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       {
          '''input_ids''': input_ids,
          '''attention_mask''': input_mask,
          '''token_type_ids''': token_type_ids,
      }
      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )
      self.parent.assertEqual(result.logits.shape				,(self.batch_size, self.seq_length, self.num_labels)    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerForQuestionAnswering(config=__lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       {
          '''input_ids''': input_ids,
          '''attention_mask''': input_mask,
          '''token_type_ids''': token_type_ids,
      }

      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )
      self.parent.assertEqual(result.start_logits.shape				,(self.batch_size, self.seq_length)    )
      self.parent.assertEqual(result.end_logits.shape				,(self.batch_size, self.seq_length)    )





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.prepare_config_and_inputs()
      (
          __SCREAMING_SNAKE_CASE	
      )      							=       config_and_inputs
      __SCREAMING_SNAKE_CASE      							=       {'''input_ids''': input_ids, '''token_type_ids''': token_type_ids, '''attention_mask''': input_mask}
      return config, inputs_dict







@require_tf
class __a(   lowerCamelCase__,   lowerCamelCase__,   unittest.TestCase			):
   __UpperCamelCase   : List[str]	      =	(
       (
           TFRoFormerModel,
           TFRoFormerForCausalLM,
           TFRoFormerForMaskedLM,
           TFRoFormerForQuestionAnswering,
           TFRoFormerForSequenceClassification,
           TFRoFormerForTokenClassification,
           TFRoFormerForMultipleChoice,
       )
       if is_tf_available()
       else ()
   )
   __UpperCamelCase   : Optional[Any]	      =	(
       {
           'feature-extraction': TFRoFormerModel,
           'fill-mask': TFRoFormerForMaskedLM,
           'question-answering': TFRoFormerForQuestionAnswering,
           'text-classification': TFRoFormerForSequenceClassification,
           'text-generation': TFRoFormerForCausalLM,
           'token-classification': TFRoFormerForTokenClassification,
           'zero-shot': TFRoFormerForSequenceClassification,
       }
       if is_tf_available()
       else {}
   )

   __UpperCamelCase   : str	      =	False
   __UpperCamelCase   : Union[str, Any]	      =	False





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

      '''simple docstring'''

      if pipeline_test_casse_name == "TextGenerationPipelineTests":
         return True

      return False





   def      UpperCAmelCase__     (					self				:			List[str]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerModelTester(self    )
      __SCREAMING_SNAKE_CASE      							=       ConfigTester(self				,config_class=__lowerCamelCase				,hidden_size=37    )





   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      self.config_tester.run_common_tests()





   def      UpperCAmelCase__     (					self				:			Optional[Any]    ):

      '''simple docstring'''

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





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_masked_lm(*__lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			int    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_lm_head(*__lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			str    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_multiple_choice(*__lowerCamelCase    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_question_answering(*__lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_sequence_classification(*__lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			List[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_token_classification(*__lowerCamelCase    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerModel.from_pretrained("""junnyu/roformer_chinese_base"""    )
      self.assertIsNotNone(__lowerCamelCase    )







@require_tf
class __a(   unittest.TestCase			):





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerForMaskedLM.from_pretrained("""junnyu/roformer_chinese_base"""    )
      __SCREAMING_SNAKE_CASE      							=       tf.constant([[0, 1, 2, 3, 4, 5]]    )
      __SCREAMING_SNAKE_CASE      							=       model(__lowerCamelCase    )[0]

      # TODO Replace vocab size
      __SCREAMING_SNAKE_CASE      							=       5_0000

      __SCREAMING_SNAKE_CASE      							=       [1, 6, vocab_size]
      self.assertEqual(output.shape				,__lowerCamelCase    )

      print(output[:, :3, :3]    )

      # TODO Replace values below with what was printed above.
      __SCREAMING_SNAKE_CASE      							=       tf.constant(
          [
              [
                  [-0.12_053_341, -1.0_264_901, 0.29_221_946],
                  [-1.5_133_783, 0.197_433, 0.15_190_607],
                  [-5.0_135_403, -3.900_256, -0.84_038_764],
              ]
          ]    )
      tf.debugging.assert_near(output[:, :3, :3]				,__lowerCamelCase				,atol=1E-4    )







@require_tf
class __a(   unittest.TestCase			):
   __UpperCamelCase   : Any	      =	1E-4





   def      UpperCAmelCase__     (					self				:			int    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       tf.constant([[4, 10]]    )
      __SCREAMING_SNAKE_CASE      							=       TFRoFormerSinusoidalPositionalEmbedding(num_positions=6				,embedding_dim=6    )

      __SCREAMING_SNAKE_CASE      							=       emba(input_ids.shape    )
      __SCREAMING_SNAKE_CASE      							=       tf.constant(
          [[0.0_000, 0.0_000, 0.0_000, 1.0_000, 1.0_000, 1.0_000], [0.8_415, 0.0_464, 0.0_022, 0.5_403, 0.9_989, 1.0_000]]    )

      tf.debugging.assert_near(__lowerCamelCase				,__lowerCamelCase				,atol=self.tolerance    )





   def      UpperCAmelCase__     (					self				:			List[str]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       tf.constant(
          [
              [0.0_000, 0.0_000, 0.0_000, 0.0_000, 0.0_000],
              [0.8_415, 0.8_219, 0.8_020, 0.7_819, 0.7_617],
              [0.9_093, 0.9_364, 0.9_581, 0.9_749, 0.9_870],
          ]    )
      __SCREAMING_SNAKE_CASE      							=       TFRoFormerSinusoidalPositionalEmbedding(num_positions=512				,embedding_dim=512    )
      emba([2, 16, 512]    )
      __SCREAMING_SNAKE_CASE      							=       emba.weight[:3, :5]

      tf.debugging.assert_near(__lowerCamelCase				,__lowerCamelCase				,atol=self.tolerance    )







@require_tf
class __a(   unittest.TestCase			):
   __UpperCamelCase   : Any	      =	1E-4





   def      UpperCAmelCase__     (					self				:			List[str]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       tf.reshape(tf.range(2 * 12 * 16 * 64				,dtype=tf.floataa    )				,shape=(2, 12, 16, 64)    ) / 100

      __SCREAMING_SNAKE_CASE      							=       -tf.reshape(tf.range(2 * 12 * 16 * 64				,dtype=tf.floataa    )				,shape=(2, 12, 16, 64)    ) / 100

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerSinusoidalPositionalEmbedding(num_positions=32				,embedding_dim=64    )
      __SCREAMING_SNAKE_CASE      							=       embed_positions([2, 16, 768]    )[None, None, :, :]

      __SCREAMING_SNAKE_CASE      							=       TFRoFormerSelfAttention.apply_rotary_position_embeddings(
          __lowerCamelCase				,__lowerCamelCase				,__lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       tf.constant(
          [
              [0.0_000, 0.0_100, 0.0_200, 0.0_300, 0.0_400, 0.0_500, 0.0_600, 0.0_700],
              [-0.2_012, 0.8_897, 0.0_263, 0.9_401, 0.2_074, 0.9_463, 0.3_481, 0.9_343],
              [-1.7_057, 0.6_271, -1.2_145, 1.3_897, -0.6_303, 1.7_647, -0.1_173, 1.8_985],
              [-2.1_731, -1.6_397, -2.7_358, 0.2_854, -2.1_840, 1.7_183, -1.3_018, 2.4_871],
              [0.2_717, -3.6_173, -2.9_206, -2.1_988, -3.6_638, 0.3_858, -2.9_155, 2.2_980],
              [3.9_859, -2.1_580, -0.7_984, -4.4_904, -4.1_181, -2.0_252, -4.4_782, 1.1_253],
          ]    )
      __SCREAMING_SNAKE_CASE      							=       tf.constant(
          [
              [0.0_000, -0.0_100, -0.0_200, -0.0_300, -0.0_400, -0.0_500, -0.0_600, -0.0_700],
              [0.2_012, -0.8_897, -0.0_263, -0.9_401, -0.2_074, -0.9_463, -0.3_481, -0.9_343],
              [1.7_057, -0.6_271, 1.2_145, -1.3_897, 0.6_303, -1.7_647, 0.1_173, -1.8_985],
              [2.1_731, 1.6_397, 2.7_358, -0.2_854, 2.1_840, -1.7_183, 1.3_018, -2.4_871],
              [-0.2_717, 3.6_173, 2.9_206, 2.1_988, 3.6_638, -0.3_858, 2.9_155, -2.2_980],
              [-3.9_859, 2.1_580, 0.7_984, 4.4_904, 4.1_181, 2.0_252, 4.4_782, -1.1_253],
          ]    )

      tf.debugging.assert_near(query_layer[0, 0, :6, :8]				,__lowerCamelCase				,atol=self.tolerance    )
      tf.debugging.assert_near(key_layer[0, 0, :6, :8]				,__lowerCamelCase				,atol=self.tolerance    )












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





