





'''simple docstring'''

import tempfile
import unittest

from transformers import SPIECE_UNDERLINE, BatchEncoding, PLBartTokenizer, 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.plbart.modeling_plbart import shift_tokens_right

a        =						50003
a        =						50002







@require_sentencepiece
@require_tokenizers
class __a (   _snake_case,   unittest.TestCase			):
   __UpperCamelCase   : Dict	      =	PLBartTokenizer
   __UpperCamelCase   : Union[str, Any]	      =	None
   __UpperCamelCase   : Union[str, Any]	      =	False





   def      UpperCAmelCase__     (					self				:			str    ):

      '''simple docstring'''

      super().setUp()

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





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       PLBartTokenizer(lowerCamelCase				,language_codes="""base"""				,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>""",
              """.""",
          ]				,)

      __SCREAMING_SNAKE_CASE      							=       tokenizer.vocab_size
      __SCREAMING_SNAKE_CASE      							=       [tokenizer.convert_ids_to_tokens(lowerCamelCase    ) for x in range(end - 4				,lowerCamelCase    )]

      self.assertListEqual(lowerCamelCase				,["""__java__""", """__python__""", """__en_XX__""", """<mask>"""]    )

      __SCREAMING_SNAKE_CASE      							=       """java.lang.Exception, python.lang.Exception, javascript, php, ruby, go"""
      __SCREAMING_SNAKE_CASE      							=       tokenizer(lowerCamelCase    ).input_ids
      self.assertEqual(
          tokenizer.decode(lowerCamelCase				,skip_special_tokens=lowerCamelCase				,clean_up_tokenization_spaces=lowerCamelCase    )				,lowerCamelCase				,)





   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       PLBartTokenizer(lowerCamelCase				,language_codes="""multi"""				,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>""",
              """.""",
          ]				,)
      __SCREAMING_SNAKE_CASE      							=       tokenizer.vocab_size
      __SCREAMING_SNAKE_CASE      							=       [tokenizer.convert_ids_to_tokens(lowerCamelCase    ) for x in range(end - 7				,lowerCamelCase    )]

      self.assertListEqual(
          lowerCamelCase				,["""__java__""", """__python__""", """__en_XX__""", """__javascript__""", """__php__""", """__ruby__""", """__go__"""]    )
      __SCREAMING_SNAKE_CASE      							=       """java.lang.Exception, python.lang.Exception, javascript, php, ruby, go"""
      __SCREAMING_SNAKE_CASE      							=       tokenizer(lowerCamelCase    ).input_ids
      self.assertEqual(
          tokenizer.decode(lowerCamelCase				,skip_special_tokens=lowerCamelCase				,clean_up_tokenization_spaces=lowerCamelCase    )				,lowerCamelCase				,)







@require_torch
@require_sentencepiece
@require_tokenizers
class __a (   unittest.TestCase			):
   __UpperCamelCase   : Optional[int]	      =	'uclanlp/plbart-python-en_XX'
   __UpperCamelCase   : Dict	      =	[
       'def maximum(a,b,c):NEW_LINE_INDENTreturn max([a,b,c])',
       'def sum(a,b,c):NEW_LINE_INDENTreturn sum([a,b,c])',
   ]
   __UpperCamelCase   : Tuple	      =	[
       'Returns the maximum value of a b c.',
       'Sums the values of a b c.',
   ]
   __UpperCamelCase   : str	      =	[
       134,
       5452,
       3_3460,
       3_3441,
       3_3463,
       3_3465,
       3_3463,
       3_3449,
       988,
       20,
       3_3456,
       19,
       3_3456,
       771,
       39,
       4258,
       889,
       3318,
       3_3441,
       3_3463,
       3_3465,
       3_3463,
       3_3449,
       2471,
       2,
       PYTHON_CODE,
   ]





   @classmethod
   def      UpperCAmelCase__     (					cls				:			Optional[int]    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       PLBartTokenizer.from_pretrained(
          cls.checkpoint_name				,language_codes="""base"""				,src_lang="""python"""				,tgt_lang="""en_XX"""    )
      __SCREAMING_SNAKE_CASE      							=       1
      return cls





   def      UpperCAmelCase__     (					self				:			Optional[int]    ):

      '''simple docstring'''

      self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["""__java__"""]				,5_0001    )
      self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["""__python__"""]				,5_0002    )
      self.assertEqual(self.tokenizer.fairseq_tokens_to_ids["""__en_XX__"""]				,5_0003    )





   def      UpperCAmelCase__     (					self				:			Dict    ):

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

      '''simple docstring'''

      self.assertIn(lowerCamelCase				,self.tokenizer.all_special_ids    )
      __SCREAMING_SNAKE_CASE      							=       [EN_CODE, 9037, 3_3442, 57, 752, 153, 14, 56, 18, 9, 2]
      __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				:			Any    ):

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       ["""def sum(a,b,c):NEW_LINE_INDENTreturn sum([a,b,c])""" * 20]
      self.assertIsInstance(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[-2]				,2    )
      self.assertEqual(ids[-1]				,lowerCamelCase    )
      self.assertEqual(len(lowerCamelCase    )				,lowerCamelCase    )





   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

      self.assertListEqual(self.tokenizer.convert_tokens_to_ids(["""<mask>""", """__java__"""]    )				,[5_0004, 5_0001]    )





   def      UpperCAmelCase__     (					self				:			Union[str, 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      							=       PLBartTokenizer.from_pretrained(lowerCamelCase    )
      self.assertDictEqual(new_tok.fairseq_tokens_to_ids				,lowerCamelCase    )





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

      '''simple docstring'''

      __SCREAMING_SNAKE_CASE      							=       self.tokenizer(self.src_text				,text_target=self.tgt_text				,padding=lowerCamelCase				,return_tensors="""pt"""    )
      __SCREAMING_SNAKE_CASE      							=       shift_tokens_right(batch["""labels"""]				,self.tokenizer.pad_token_id    )

      # fairseq batch: https://gist.github.com/sshleifer/cba08bc2109361a74ac3760a7e30e4f4
      self.assertEqual(batch.input_ids[1][-2:].tolist()				,[2, PYTHON_CODE]    )
      self.assertEqual(batch.decoder_input_ids[1][0]				,lowerCamelCase    )
      self.assertEqual(batch.decoder_input_ids[1][-1]				,2    )
      self.assertEqual(batch.labels[1][-2:].tolist()				,[2, EN_CODE]    )





   @require_torch
   def      UpperCAmelCase__     (					self				:			Tuple    ):

      '''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.assertIsInstance(lowerCamelCase				,lowerCamelCase    )

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





   def      UpperCAmelCase__     (					self				:			str    ):

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

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





   @require_torch
   def      UpperCAmelCase__     (					self				:			Any    ):

      '''simple docstring'''

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

      self.assertEqual(
          nested_simplify(lowerCamelCase    )				,{
              # A, test, EOS, en_XX
              """input_ids""": [[150, 242, 2, 5_0003]],
              """attention_mask""": [[1, 1, 1, 1]],
              # java
              """forced_bos_token_id""": 5_0001,
          }				,)












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





