
import unittest

from transformers.models.xlm_prophetnet.tokenization_xlm_prophetnet import SPIECE_UNDERLINE, XLMProphetNetTokenizer
from transformers.testing_utils import get_tests_dir, require_sentencepiece, slow
from transformers.utils import cached_property

from ...test_tokenization_common import TokenizerTesterMixin


__a         =   get_tests_dir('fixtures/test_sentencepiece.model')
@require_sentencepiece
class 					lowercase__(							UpperCAmelCase					,		unittest.TestCase				):



	"""simple docstring"""




	a     :Optional[int]       	=      XLMProphetNetTokenizer
	a     :Any       	=      False
	a     :Optional[int]       	=      True
	def 		_lowercase    (			self    :     Optional[int]			)			->	List[str]:
					super().setUp()

					# We have a SentencePiece fixture for testing
					lowercase_	    =   XLMProphetNetTokenizer(SCREAMING_SNAKE_CASE_			,				keep_accents=SCREAMING_SNAKE_CASE_			)
					tokenizer.save_pretrained(self.tmpdirname			)
	def 		_lowercase    (			self    :     Any			)			->	Optional[Any]:
					lowercase_	    =   '''[PAD]'''
					lowercase_	    =   0

					self.assertEqual(self.get_tokenizer()._convert_token_to_id(SCREAMING_SNAKE_CASE_			)			,				SCREAMING_SNAKE_CASE_			)
					self.assertEqual(self.get_tokenizer()._convert_id_to_token(SCREAMING_SNAKE_CASE_			)			,				SCREAMING_SNAKE_CASE_			)
	def 		_lowercase    (			self    :     Optional[Any]			)			->	int:
					lowercase_	    =   list(self.get_tokenizer().get_vocab().keys()			)

					self.assertEqual(vocab_keys[0]			,				'''[PAD]'''			)
					self.assertEqual(vocab_keys[1]			,				'''[CLS]'''			)
					self.assertEqual(vocab_keys[-1]			,				'''j'''			)
					self.assertEqual(len(SCREAMING_SNAKE_CASE_			)			,				1_0_1_2			)
	def 		_lowercase    (			self    :     int			)			->	int:
					self.assertEqual(self.get_tokenizer().vocab_size			,				1_0_1_2			)
	def 		_lowercase    (			self    :     Union[str, Any]			)			->	Union[str, Any]:
					lowercase_	    =   XLMProphetNetTokenizer(SCREAMING_SNAKE_CASE_			,				keep_accents=SCREAMING_SNAKE_CASE_			)

					lowercase_	    =   tokenizer.tokenize('''This is a test'''			)
					self.assertListEqual(SCREAMING_SNAKE_CASE_			,				['''▁This''', '''▁is''', '''▁a''', '''▁t''', '''est''']			)

					self.assertListEqual(
					    tokenizer.convert_tokens_to_ids(SCREAMING_SNAKE_CASE_			)			,				[value + tokenizer.fairseq_offset for value in [2_8_5, 4_6, 1_0, 1_7_0, 3_8_2]]			,				)

					lowercase_	    =   tokenizer.tokenize('''I was born in 92000, and this is falsé.'''			)
					self.assertListEqual(
					    SCREAMING_SNAKE_CASE_			,				[
					        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''',
					        '''é''',
					        '''.''',
					    ]			,				)
					lowercase_	    =   tokenizer.convert_tokens_to_ids(SCREAMING_SNAKE_CASE_			)
					self.assertListEqual(
					    SCREAMING_SNAKE_CASE_			,				[
					        value + tokenizer.fairseq_offset
					        for value in [8, 2_1, 8_4, 5_5, 2_4, 1_9, 7, -9, 6_0_2, 3_4_7, 3_4_7, 3_4_7, 3, 1_2, 6_6, 4_6, 7_2, 8_0, 6, -9, 4]
					    ]			,				)

					lowercase_	    =   tokenizer.convert_ids_to_tokens(SCREAMING_SNAKE_CASE_			)
					self.assertListEqual(
					    SCREAMING_SNAKE_CASE_			,				[
					        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]''',
					        '''.''',
					    ]			,				)
	@cached_property
	def 		_lowercase    (			self    :     Tuple			)			->	List[Any]:
					return XLMProphetNetTokenizer.from_pretrained('''microsoft/xprophetnet-large-wiki100-cased'''			)
	@slow
	def 		_lowercase    (			self    :     Optional[int]			)			->	Union[str, Any]:
					lowercase_	    =   '''Hello World!'''
					lowercase_	    =   [3_5_3_8_9, 6_6_7_2, 4_9, 2]
					self.assertListEqual(SCREAMING_SNAKE_CASE_			,				self.big_tokenizer.encode(SCREAMING_SNAKE_CASE_			)			)




	@slow
	def 		_lowercase    (			self    :     Any			)			->	List[Any]:
					# fmt: off
					lowercase_	    =   {'''input_ids''': [[1_1_0_7_3, 8_2_7_8_3, 1_8, 2_6, 8_2_7_8_3, 5_4_9, 5_1_5_4_0, 2_4_8, 1_7_2_0_9, 1_3_0_1, 2_1_7, 2_0, 2_1_5_1_8_6, 1_3_2_5, 1_4_7, 1_7_2_0_9, 1_3_0_1, 2_1_7, 2_0, 5_6_3_7_0, 5_3, 1_2_2_0_2_0, 2_0, 1_6_4_7_7, 2_7, 8_7_3_5_5, 4_5_4_8, 2_0, 4_7_2_8, 7_8_3_9_2, 1_7, 1_5_9_9_6_9, 1_8, 2_6, 2_4_4_9_1, 6_2_9, 1_5, 5_3_8, 2_2_7_0_4, 5_4_3_9, 1_5, 2_7_8_8, 2_4_4_9_1, 9_8_8_5, 1_5, 4_3_5_3_4, 6_0_5, 1_5, 8_1_4, 1_8_4_0_3, 3_3_2_0_0, 2_9, 1_5, 4_3_5_3_4, 2_4_4_5_8, 1_2_4_1_0, 1_1_1, 2_4_9_6_6, 8_3_6_6_9, 9_6_3_7, 1_4_4_0_6_8, 2_6, 8_5_0, 2_2_3_4_6, 2_7, 1_4_7, 2_4_9_6_6, 8_3_6_6_9, 8_3_4_9_0, 2_6, 3_9_1_1_3, 7_3_5, 2_7, 6_8_9, 6_5_6, 2_8_0_0, 1_3_3_9, 4_6_0_0, 5_3, 1_2_2_0_2_0, 1_1_5_7_8_5, 3_4, 8_1_6, 1_3_3_9, 4_6_8_8_7, 1_8, 1_4_7, 5_3_9_0_5, 1_9_5_1, 4_2_2_3_8, 4_1_1_7_0, 1_7_7_3_2, 8_3_4, 4_3_6, 1_5, 2_7_5_2_3, 9_8_7_3_3, 2_1_7, 1_4_7, 5_5_4_2, 4_9_8_1, 9_3_0, 1_7_3_4_7, 1_6, 2], [2_0_0_9_1, 6_2_9, 9_4, 8_2_7_8_6, 5_8, 4_9_0, 2_0, 1_5_2_8, 8_4, 5_3_9_0_5, 3_4_4, 8_0_5_9_2, 1_1_0_1_2_8, 1_8_8_2_2, 5_2_6_7, 1_3_0_6, 6_2, 1_5_2_5_3_7, 3_0_8, 7_9_9_7, 4_0_1, 1_2_4_4_2_7, 5_4_9, 3_5_4_4_2, 2_2_5, 1_0_9, 1_5_0_5_5, 2_5_7_4_8, 1_4_7, 7_1_1_9, 4_3_7_1_2, 3_4, 7_6_7, 1_3_5_3_6_6, 1_8, 1_6, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [5_9_2, 6_3_7_8_4, 1_1_9_4_6_6, 1_7, 1_4_7_8_0_8, 8_8_2_1_4, 1_8, 6_5_6, 8_1, 3_2, 3_2_9_6, 1_0_2_8_0, 1_6, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], '''attention_mask''': [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]}  # noqa: E501
					# fmt: on

					self.tokenizer_integration_test_util(
					    expected_encoding=SCREAMING_SNAKE_CASE_			,				model_name='''microsoft/xprophetnet-large-wiki100-cased'''			,				revision='''1acad1643ddd54a44df6a1b797ada8373685d90e'''			,				)








'''simple docstring'''



import sys
from collections import defaultdict





class   UpperCAmelCase_    :





    """simple docstring"""






    def __init__(				self      )							->	int:
         __lowerCamelCase  :      Any														=						[]







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_      )							->	Any:
         return self.node_position[vertex]







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Tuple:
         __lowerCamelCase  :      Optional[int]														=						pos







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	int:
         if start > size // 2 - 1:
              return
         else:
              if 2 * start + 2 >= size:
                   __lowerCamelCase  :      str														=						2 * start + 1
              else:
                   if heap[2 * start + 1] < heap[2 * start + 2]:
                        __lowerCamelCase  :      Optional[Any]														=						2 * start + 1
                   else:
                        __lowerCamelCase  :      int														=						2 * start + 2
              if heap[smallest_child] < heap[start]:
                   __lowerCamelCase							,			__lowerCamelCase  :      Optional[Any]														=						heap[smallest_child], positions[smallest_child]
                   __lowerCamelCase							,			__lowerCamelCase  :      int														=						(
                       heap[start],
                       positions[start],
                   )
                   __lowerCamelCase							,			__lowerCamelCase  :      str														=						temp, tempa

                   __lowerCamelCase  :      Dict														=						self.get_position(positions[smallest_child]      )
                   self.set_position(
                       positions[smallest_child]     ,	self.get_position(positions[start]      )      )
                   self.set_position(positions[start]     ,	SCREAMING_SNAKE_CASE_      )

                   self.top_to_bottom(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Any:
         __lowerCamelCase  :      Any														=						position[index]

         while index != 0:
              __lowerCamelCase  :      Union[str, Any]														=						int((index - 2) / 2      ) if index % 2 == 0 else int((index - 1) / 2      )

              if val < heap[parent]:
                   __lowerCamelCase  :      Union[str, Any]														=						heap[parent]
                   __lowerCamelCase  :      Any														=						position[parent]
                   self.set_position(position[parent]     ,	SCREAMING_SNAKE_CASE_      )
              else:
                   __lowerCamelCase  :      Tuple														=						val
                   __lowerCamelCase  :      List[str]														=						temp
                   self.set_position(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
                   break
              __lowerCamelCase  :      Tuple														=						parent
         else:
              __lowerCamelCase  :      Union[str, Any]														=						val
              __lowerCamelCase  :      Tuple														=						temp
              self.set_position(SCREAMING_SNAKE_CASE_     ,	0      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Optional[int]:
         __lowerCamelCase  :      Optional[int]														=						len(SCREAMING_SNAKE_CASE_      ) // 2 - 1
         for i in range(SCREAMING_SNAKE_CASE_     ,	-1     ,	-1      ):
              self.top_to_bottom(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	len(SCREAMING_SNAKE_CASE_      )     ,	SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	List[Any]:
         __lowerCamelCase  :      Any														=						positions[0]
         __lowerCamelCase  :      Union[str, Any]														=						sys.maxsize
         self.top_to_bottom(SCREAMING_SNAKE_CASE_     ,	0     ,	len(SCREAMING_SNAKE_CASE_      )     ,	SCREAMING_SNAKE_CASE_      )
         return temp







def      UpperCAmelCase__   (      UpperCAmelCase_       :							Optional[int]				)	->						str:
     __lowerCamelCase  :      List[Any]														=						Heap()

     __lowerCamelCase  :      Optional[int]														=						[0] * len(UpperCAmelCase_				)
     __lowerCamelCase  :      str														=						[-1] * len(UpperCAmelCase_				)  # Neighboring Tree Vertex of selected vertex
     # Minimum Distance of explored vertex with neighboring vertex of partial tree
     # formed in graph
     __lowerCamelCase  :      List[str]														=						[]  # Heap of Distance of vertices from their neighboring vertex
     __lowerCamelCase  :      Tuple														=						[]

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

     __lowerCamelCase  :      Tuple														=						[]
     __lowerCamelCase  :      Dict														=						1
     __lowerCamelCase  :      str														=						sys.maxsize
     for neighbor, distance in adjacency_list[0]:
          __lowerCamelCase  :      Any														=						0
          __lowerCamelCase  :      Any														=						distance
     heap.heapify(UpperCAmelCase_ ,       UpperCAmelCase_				)

     for _ in range(1 ,       len(UpperCAmelCase_				)				):
          __lowerCamelCase  :      List[Any]														=						heap.delete_minimum(UpperCAmelCase_ ,       UpperCAmelCase_				)
          if visited[vertex] == 0:
               tree_edges.append((nbr_tv[vertex], vertex)				)
               __lowerCamelCase  :      Union[str, Any]														=						1
               for neighbor, distance in adjacency_list[vertex]:
                    if (
                        visited[neighbor] == 0
                        and distance < distance_tv[heap.get_position(UpperCAmelCase_				)]
                    ):
                         __lowerCamelCase  :      Dict														=						distance
                         heap.bottom_to_top(
                             UpperCAmelCase_ ,       heap.get_position(UpperCAmelCase_				) ,       UpperCAmelCase_ ,       UpperCAmelCase_				)
                         __lowerCamelCase  :      str														=						vertex
     return tree_edges


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






