





'''simple docstring'''

import shutil
import tempfile
import unittest

from transformers import (
    SPIECE_UNDERLINE,
    AddedToken,
    BatchEncoding,
    NllbTokenizer,
    NllbTokenizerFast,
    is_torch_available,
)
from transformers.testing_utils import (
    get_tests_dir,
    nested_simplify,
    require_sentencepiece,
    require_tokenizers,
    require_torch,
)

from ...test_tokenization_common import TokenizerTesterMixin


a        =						get_tests_dir("fixtures/test_sentencepiece.model")


if is_torch_available():
    from transformers.models.mam_aaa.modeling_mam_aaa import shift_tokens_right

a        =						256047
a        =						256145







@require_sentencepiece
@require_tokenizers
class __a (   _snake_case,   unittest.TestCase			):
   __UpperCamelCase   : List[str]	      =	NllbTokenizer
   __UpperCamelCase   : Union[str, Any]	      =	NllbTokenizerFast
   __UpperCamelCase   : Union[str, Any]	      =	True
   __UpperCamelCase   : Dict	      =	True
   __UpperCamelCase   : Optional[Any]	      =	{}





   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      super().setUp()

      # We have a SentencePiece fixture for testing
      __SCREAMING_SNAKE_CASE      							=       NllbTokenizer(lowerCamelCase				,keep_accents=lowerCamelCase    )
      tokenizer.save_pretrained(self.tmpdirname    )





   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       NllbTokenizer(lowerCamelCase				,keep_accents=lowerCamelCase    )

      __SCREAMING_SNAKE_CASE      							=       tokenizer.tokenize("""This is a test"""    )
      self.assertListEqual(lowerCamelCase				,["""▁This""", """▁is""", """▁a""", """▁t""", """est"""]    )

      self.assertListEqual(
          tokenizer.convert_tokens_to_ids(lowerCamelCase    )				,[value + tokenizer.fairseq_offset for value in [285, 46, 10, 170, 382]]				,)

      __SCREAMING_SNAKE_CASE      							=       tokenizer.tokenize("""I was born in 92000, and this is falsé."""    )
      self.assertListEqual(
          lowerCamelCase				,[
              SPIECE_UNDERLINE + """I""",
              SPIECE_UNDERLINE + """was""",
              SPIECE_UNDERLINE + """b""",
              """or""",
              """n""",
              SPIECE_UNDERLINE + """in""",
              SPIECE_UNDERLINE + """""",
              """9""",
              """2""",
              """0""",
              """0""",
              """0""",
              """,""",
              SPIECE_UNDERLINE + """and""",
              SPIECE_UNDERLINE + """this""",
              SPIECE_UNDERLINE + """is""",
              SPIECE_UNDERLINE + """f""",
              """al""",
              """s""",
              """é""",
              """.""",
          ]				,)
      __SCREAMING_SNAKE_CASE      							=       tokenizer.convert_tokens_to_ids(lowerCamelCase    )
      self.assertListEqual(
          lowerCamelCase				,[
              value + tokenizer.fairseq_offset
              for value in [8, 21, 84, 55, 24, 19, 7, 2, 602, 347, 347, 347, 3, 12, 66, 46, 72, 80, 6, 2, 4]
          ]				,)

      __SCREAMING_SNAKE_CASE      							=       tokenizer.convert_ids_to_tokens(lowerCamelCase    )
      self.assertListEqual(
          lowerCamelCase				,[
              SPIECE_UNDERLINE + """I""",
              SPIECE_UNDERLINE + """was""",
              SPIECE_UNDERLINE + """b""",
              """or""",
              """n""",
              SPIECE_UNDERLINE + """in""",
              SPIECE_UNDERLINE + """""",
              """<unk>""",
              """2""",
              """0""",
              """0""",
              """0""",
              """,""",
              SPIECE_UNDERLINE + """and""",
              SPIECE_UNDERLINE + """this""",
              SPIECE_UNDERLINE + """is""",
              SPIECE_UNDERLINE + """f""",
              """al""",
              """s""",
              """<unk>""",
              """.""",
          ]				,)





   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       (self.rust_tokenizer_class, """hf-internal-testing/tiny-random-nllb""", {})
      for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
         with self.subTest(f"""{tokenizer.__class__.__name__} ({pretrained_name})"""    ):
            __SCREAMING_SNAKE_CASE      							=       self.rust_tokenizer_class.from_pretrained(lowerCamelCase				,**lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       self.tokenizer_class.from_pretrained(lowerCamelCase				,**lowerCamelCase    )

            __SCREAMING_SNAKE_CASE      							=       tempfile.mkdtemp()

            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.save_pretrained(lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       tokenizer_p.save_pretrained(lowerCamelCase    )

            # Checks it save with the same files + the tokenizer.json file for the fast one
            self.assertTrue(any("""tokenizer.json""" in f for f in tokenizer_r_files    )    )
            __SCREAMING_SNAKE_CASE      							=       tuple(f for f in tokenizer_r_files if """tokenizer.json""" not in f    )
            self.assertSequenceEqual(lowerCamelCase				,lowerCamelCase    )

            # Checks everything loads correctly in the same way
            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.from_pretrained(lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       tokenizer_p.from_pretrained(lowerCamelCase    )

            # Check special tokens are set accordingly on Rust and Python
            for key in tokenizer_pp.special_tokens_map:
               self.assertTrue(hasattr(lowerCamelCase				,lowerCamelCase    )    )

            shutil.rmtree(lowerCamelCase    )

            # Save tokenizer rust, legacy_format=True
            __SCREAMING_SNAKE_CASE      							=       tempfile.mkdtemp()

            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.save_pretrained(lowerCamelCase				,legacy_format=lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       tokenizer_p.save_pretrained(lowerCamelCase    )

            # Checks it save with the same files
            self.assertSequenceEqual(lowerCamelCase				,lowerCamelCase    )

            # Checks everything loads correctly in the same way
            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.from_pretrained(lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       tokenizer_p.from_pretrained(lowerCamelCase    )

            # Check special tokens are set accordingly on Rust and Python
            for key in tokenizer_pp.special_tokens_map:
               self.assertTrue(hasattr(lowerCamelCase				,lowerCamelCase    )    )

            shutil.rmtree(lowerCamelCase    )

            # Save tokenizer rust, legacy_format=False
            __SCREAMING_SNAKE_CASE      							=       tempfile.mkdtemp()

            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.save_pretrained(lowerCamelCase				,legacy_format=lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       tokenizer_p.save_pretrained(lowerCamelCase    )

            # Checks it saved the tokenizer.json file
            self.assertTrue(any("""tokenizer.json""" in f for f in tokenizer_r_files    )    )

            # Checks everything loads correctly in the same way
            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.from_pretrained(lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       tokenizer_p.from_pretrained(lowerCamelCase    )

            # Check special tokens are set accordingly on Rust and Python
            for key in tokenizer_pp.special_tokens_map:
               self.assertTrue(hasattr(lowerCamelCase				,lowerCamelCase    )    )

            shutil.rmtree(lowerCamelCase    )





   @require_torch
   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      if not self.test_seqaseq:
         return

      __SCREAMING_SNAKE_CASE      							=       self.get_tokenizers()
      for tokenizer in tokenizers:
         with self.subTest(f"""{tokenizer.__class__.__name__}"""    ):
            # Longer text that will definitely require truncation.
            __SCREAMING_SNAKE_CASE      							=       [
                """ UN Chief Says There Is No Military Solution in Syria""",
                """ Secretary-General Ban Ki-moon says his response to Russia's stepped up military support for"""
                """ Syria is that 'there is no military solution' to the nearly five-year conflict and more weapons"""
                """ will only worsen the violence and misery for millions of people.""",
            ]
            __SCREAMING_SNAKE_CASE      							=       [
                """Şeful ONU declară că nu există o soluţie militară în Siria""",
                """Secretarul General Ban Ki-moon declară că răspunsul său la intensificarea sprijinului militar al"""
                """ Rusiei pentru Siria este că \"nu există o soluţie militară\" la conflictul de aproape cinci ani şi"""
                """ că noi arme nu vor face decât să înrăutăţească violenţele şi mizeria pentru milioane de oameni.""",
            ]
            try:
               __SCREAMING_SNAKE_CASE      							=       tokenizer.prepare_seqaseq_batch(
                   src_texts=lowerCamelCase				,tgt_texts=lowerCamelCase				,max_length=3				,max_target_length=10				,return_tensors="""pt"""				,src_lang="""eng_Latn"""				,tgt_lang="""ron_Latn"""				,)
            except NotImplementedError:
               return
            self.assertEqual(batch.input_ids.shape[1]				,3    )
            self.assertEqual(batch.labels.shape[1]				,10    )
            # max_target_length will default to max_length if not specified
            __SCREAMING_SNAKE_CASE      							=       tokenizer.prepare_seqaseq_batch(
                lowerCamelCase				,tgt_texts=lowerCamelCase				,max_length=3				,return_tensors="""pt"""    )
            self.assertEqual(batch.input_ids.shape[1]				,3    )
            self.assertEqual(batch.labels.shape[1]				,3    )

            __SCREAMING_SNAKE_CASE      							=       tokenizer.prepare_seqaseq_batch(
                src_texts=lowerCamelCase				,max_length=3				,max_target_length=10				,return_tensors="""pt"""    )
            self.assertEqual(batch_encoder_only.input_ids.shape[1]				,3    )
            self.assertEqual(batch_encoder_only.attention_mask.shape[1]				,3    )
            self.assertNotIn("""decoder_input_ids"""				,lowerCamelCase    )





   @unittest.skip("""Unfortunately way too slow to build a BPE with SentencePiece."""    )
   def      UpperCAmelCase__     (					self				:			List[str]    ):

      '''simple docstring'''

      pass





   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
         with self.subTest(f"""{tokenizer.__class__.__name__} ({pretrained_name})"""    ):
            __SCREAMING_SNAKE_CASE      							=       [AddedToken("""<special>"""				,lstrip=lowerCamelCase    )]

            __SCREAMING_SNAKE_CASE      							=       self.rust_tokenizer_class.from_pretrained(
                lowerCamelCase				,additional_special_tokens=lowerCamelCase				,**lowerCamelCase    )
            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.encode("""Hey this is a <special> token"""    )

            __SCREAMING_SNAKE_CASE      							=       tokenizer_r.encode("""<special>"""				,add_special_tokens=lowerCamelCase    )[0]

            self.assertTrue(special_token_id in r_output    )

            if self.test_slow_tokenizer:
               __SCREAMING_SNAKE_CASE      							=       self.rust_tokenizer_class.from_pretrained(
                   lowerCamelCase				,additional_special_tokens=lowerCamelCase				,**lowerCamelCase				,)
               __SCREAMING_SNAKE_CASE      							=       self.tokenizer_class.from_pretrained(
                   lowerCamelCase				,additional_special_tokens=lowerCamelCase				,**lowerCamelCase    )

               __SCREAMING_SNAKE_CASE      							=       tokenizer_p.encode("""Hey this is a <special> token"""    )

               __SCREAMING_SNAKE_CASE      							=       tokenizer_cr.encode("""Hey this is a <special> token"""    )

               self.assertEqual(lowerCamelCase				,lowerCamelCase    )
               self.assertEqual(lowerCamelCase				,lowerCamelCase    )
               self.assertTrue(special_token_id in p_output    )
               self.assertTrue(special_token_id in cr_output    )







@require_torch
@require_sentencepiece
@require_tokenizers
class __a (   unittest.TestCase			):
   __UpperCamelCase   : Tuple	      =	'facebook/nllb-200-distilled-600M'
   __UpperCamelCase   : Union[str, Any]	      =	[
       ' UN Chief Says There Is No Military Solution in Syria',
       ' Secretary-General Ban Ki-moon says his response to Russia\'s stepped up military support for Syria is that "there is no military solution" to the nearly five-year conflict and more weapons will only worsen the violence and misery for millions of people.',
   ]
   __UpperCamelCase   : List[Any]	      =	[
       'Şeful ONU declară că nu există o soluţie militară în Siria',
       'Secretarul General Ban Ki-moon declară că răspunsul său la intensificarea sprijinului militar al Rusiei'
       ' pentru Siria este că "nu există o soluţie militară" la conflictul de aproape cinci ani şi că noi arme nu vor'
       ' face decât să înrăutăţească violenţele şi mizeria pentru milioane de oameni.',
   ]
   __UpperCamelCase   : Dict	      =	[
       25_6047,
       1_6297,
       13_4408,
       8165,
       24_8066,
       1_4734,
       950,
       1135,
       10_5721,
       3573,
       83,
       2_7352,
       108,
       4_9486,
       2,
   ]





   @classmethod
   def      UpperCAmelCase__     (					cls				:			str    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       NllbTokenizer.from_pretrained(
          cls.checkpoint_name				,src_lang="""eng_Latn"""				,tgt_lang="""ron_Latn"""    )
      __SCREAMING_SNAKE_CASE      							=       1
      return cls





   def      UpperCAmelCase__     (					self				:			Tuple    ):

      '''simple docstring'''

      self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["""ace_Arab"""]				,25_6001    )
      self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["""ace_Latn"""]				,25_6002    )
      self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["""fra_Latn"""]				,25_6057    )





   def      UpperCAmelCase__     (					self				:			int    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.tokenizer.batch_encode_plus(self.src_text    ).input_ids[0]
      self.assertListEqual(self.expected_src_tokens				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      self.assertIn(lowerCamelCase				,self.tokenizer.all_special_ids    )
      # fmt: off
      __SCREAMING_SNAKE_CASE      							=       [RO_CODE, 4254, 9_8068, 11_2923, 3_9072, 3909, 713, 10_2767, 26, 1_7314, 3_5642, 1_4683, 3_3118, 2022, 6_6987, 2, 25_6047]
      # fmt: on

      __SCREAMING_SNAKE_CASE      							=       self.tokenizer.decode(lowerCamelCase				,skip_special_tokens=lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       self.tokenizer.decode(generated_ids[1:]				,skip_special_tokens=lowerCamelCase    )
      self.assertEqual(lowerCamelCase				,lowerCamelCase    )
      self.assertNotIn(self.tokenizer.eos_token				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Dict    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       ["""this is gunna be a long sentence """ * 20]
      assert isinstance(src_text[0]				,lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       10
      __SCREAMING_SNAKE_CASE      							=       self.tokenizer(lowerCamelCase				,max_length=lowerCamelCase				,truncation=lowerCamelCase    ).input_ids[0]
      self.assertEqual(ids[-1]				,2    )
      self.assertEqual(ids[0]				,lowerCamelCase    )
      self.assertEqual(len(lowerCamelCase    )				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Tuple    ):

      '''simple docstring'''

      self.assertListEqual(self.tokenizer.convert_tokens_to_ids(["""<mask>""", """ar_AR"""]    )				,[25_6203, 3]    )





   def      UpperCAmelCase__     (					self				:			Optional[Any]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       tempfile.mkdtemp()
      __SCREAMING_SNAKE_CASE      							=       self.tokenizer.fairseq_tokens_to_ids
      self.tokenizer.save_pretrained(lowerCamelCase    )
      __SCREAMING_SNAKE_CASE      							=       NllbTokenizer.from_pretrained(lowerCamelCase    )
      self.assertDictEqual(new_tok.fairseq_tokens_to_ids				,lowerCamelCase    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.tokenizer(
          self.src_text				,text_target=self.tgt_text				,padding=lowerCamelCase				,truncation=lowerCamelCase				,max_length=len(self.expected_src_tokens    )				,return_tensors="""pt"""				,)
      __SCREAMING_SNAKE_CASE      							=       shift_tokens_right(
          batch["""labels"""]				,self.tokenizer.pad_token_id				,self.tokenizer.lang_code_to_id["""ron_Latn"""]    )

      self.assertIsInstance(lowerCamelCase				,lowerCamelCase    )

      self.assertEqual((2, 15)				,batch.input_ids.shape    )
      self.assertEqual((2, 15)				,batch.attention_mask.shape    )
      __SCREAMING_SNAKE_CASE      							=       batch.input_ids.tolist()[0]
      self.assertListEqual(self.expected_src_tokens				,lowerCamelCase    )
      self.assertEqual(lowerCamelCase				,batch.decoder_input_ids[0, 0]    )  # EOS
      # Test that special tokens are reset
      self.assertEqual(self.tokenizer.prefix_tokens				,[EN_CODE]    )
      self.assertEqual(self.tokenizer.suffix_tokens				,[self.tokenizer.eos_token_id]    )





   def      UpperCAmelCase__     (					self				:			Tuple    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.tokenizer(self.src_text				,padding=lowerCamelCase				,truncation=lowerCamelCase				,max_length=3				,return_tensors="""pt"""    )
      __SCREAMING_SNAKE_CASE      							=       self.tokenizer(
          text_target=self.tgt_text				,padding=lowerCamelCase				,truncation=lowerCamelCase				,max_length=10				,return_tensors="""pt"""    )
      __SCREAMING_SNAKE_CASE      							=       targets["""input_ids"""]
      __SCREAMING_SNAKE_CASE      							=       shift_tokens_right(
          lowerCamelCase				,self.tokenizer.pad_token_id				,decoder_start_token_id=self.tokenizer.lang_code_to_id[self.tokenizer.tgt_lang]				,)

      self.assertEqual(batch.input_ids.shape[1]				,3    )
      self.assertEqual(batch.decoder_input_ids.shape[1]				,10    )





   @require_torch
   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.tokenizer._build_translation_inputs(
          """A test"""				,return_tensors="""pt"""				,src_lang="""eng_Latn"""				,tgt_lang="""fra_Latn"""    )

      self.assertEqual(
          nested_simplify(lowerCamelCase    )				,{
              # A, test, EOS, en_XX
              """input_ids""": [[25_6047, 70, 7356, 2]],
              """attention_mask""": [[1, 1, 1, 1]],
              # ar_AR
              """forced_bos_token_id""": 25_6057,
          }				,)





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       True
      __SCREAMING_SNAKE_CASE      							=       self.tokenizer(
          """UN Chief says there is no military solution in Syria"""				,src_lang="""eng_Latn"""				,tgt_lang="""fra_Latn"""    )
      self.assertEqual(
          inputs.input_ids				,[1_6297, 13_4408, 2_5653, 6370, 248, 254, 10_3929, 9_4995, 108, 4_9486, 2, 25_6047]    )

      __SCREAMING_SNAKE_CASE      							=       False
      __SCREAMING_SNAKE_CASE      							=       self.tokenizer(
          """UN Chief says there is no military solution in Syria"""				,src_lang="""eng_Latn"""				,tgt_lang="""fra_Latn"""    )
      self.assertEqual(
          inputs.input_ids				,[25_6047, 1_6297, 13_4408, 2_5653, 6370, 248, 254, 10_3929, 9_4995, 108, 4_9486, 2]    )












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





