


import pickle
import shutil
import tempfile
import unittest

from transformers import SPIECE_UNDERLINE, XLMRobertaTokenizer, XLMRobertaTokenizerFast
from transformers.testing_utils import get_tests_dir, require_sentencepiece, require_tokenizers, slow
from transformers.utils import cached_property

from ...test_tokenization_common import TokenizerTesterMixin


_lowercase       :      int	=	get_tests_dir("fixtures/test_sentencepiece.model")






@require_sentencepiece
@require_tokenizers
class       _UpperCamelCase    (					__snake_case    ,		unittest.TestCase				):

				"""simple docstring"""







				lowerCAmelCase 		= XLMRobertaTokenizer
				lowerCAmelCase 		= XLMRobertaTokenizerFast
				lowerCAmelCase 		= True
				lowerCAmelCase 		= True

				def      _UpperCAmelCase					(						self   )	->				Tuple:
					super().setUp()

					# We have a SentencePiece fixture for testing
					A								=				XLMRobertaTokenizer(a__				,   keep_accents=a__   )
					tokenizer.save_pretrained(self.tmpdirname   )

				def      _UpperCAmelCase					(						self   )	->				Tuple:
					A								=				"""<pad>"""
					A								=				1

					self.assertEqual(self.get_tokenizer()._convert_token_to_id(a__   )				,   a__   )
					self.assertEqual(self.get_tokenizer()._convert_id_to_token(a__   )				,   a__   )

				def      _UpperCAmelCase					(						self   )	->				Any:
					A								=				list(self.get_tokenizer().get_vocab().keys()   )

					self.assertEqual(vocab_keys[0]				,   """<s>"""   )
					self.assertEqual(vocab_keys[1]				,   """<pad>"""   )
					self.assertEqual(vocab_keys[-1]				,   """<mask>"""   )
					self.assertEqual(len(a__   )				,   1002   )

				def      _UpperCAmelCase					(						self   )	->				Tuple:
					self.assertEqual(self.get_tokenizer().vocab_size				,   1002   )

				def      _UpperCAmelCase					(						self   )	->				str:
					A								=				XLMRobertaTokenizer(a__				,   keep_accents=a__   )

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

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

					A								=				tokenizer.tokenize("""I was born in 92000, and this is falsé."""   )
					self.assertListEqual(
					    a__				,   [
					        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""",
					        """é""",
					        """.""",
					    ]				,   )
					A								=				tokenizer.convert_tokens_to_ids(a__   )
					self.assertListEqual(
					    a__				,   [
					        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]
					        #                                       ^ unk: 2 + 1 = 3                  unk: 2 + 1 = 3 ^
					    ]				,   )

					A								=				tokenizer.convert_ids_to_tokens(a__   )
					self.assertListEqual(
					    a__				,   [
					        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:
					if not self.test_slow_tokenizer:
						# as we don't have a slow version, we can't compare the outputs between slow and fast versions
						return

					A								=				(self.rust_tokenizer_class, """hf-internal-testing/tiny-xlm-roberta""", {})
					for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
						with self.subTest(f'{tokenizer.__class__.__name__} ({pretrained_name})'   ):
							A								=				self.rust_tokenizer_class.from_pretrained(a__				,   **a__   )
							A								=				self.tokenizer_class.from_pretrained(a__				,   **a__   )

							A								=				tempfile.mkdtemp()

							A								=				tokenizer_r.save_pretrained(a__   )
							A								=				tokenizer_p.save_pretrained(a__   )

							# 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   )   )
							A								=				tuple(f for f in tokenizer_r_files if """tokenizer.json""" not in f   )
							self.assertSequenceEqual(a__				,   a__   )

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

							# Check special tokens are set accordingly on Rust and Python
							for key in tokenizer_pp.special_tokens_map:
								self.assertTrue(hasattr(a__				,   a__   )   )
								# self.assertEqual(getattr(tokenizer_rp, key), getattr(tokenizer_pp, key))
								# self.assertEqual(getattr(tokenizer_rp, key + "_id"), getattr(tokenizer_pp, key + "_id"))

							shutil.rmtree(a__   )

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

							A								=				tokenizer_r.save_pretrained(a__				,   legacy_format=a__   )
							A								=				tokenizer_p.save_pretrained(a__   )

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

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

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

							shutil.rmtree(a__   )

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

							A								=				tokenizer_r.save_pretrained(a__				,   legacy_format=a__   )
							A								=				tokenizer_p.save_pretrained(a__   )

							# 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
							A								=				tokenizer_r.from_pretrained(a__   )
							A								=				tokenizer_p.from_pretrained(a__   )

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

							shutil.rmtree(a__   )

				@cached_property
				def      _UpperCAmelCase					(						self   )	->				Optional[int]:
					return XLMRobertaTokenizer.from_pretrained("""xlm-roberta-base"""   )

				def      _UpperCAmelCase					(						self   )	->				int:
					with tempfile.NamedTemporaryFile() as f:
						shutil.copyfile(a__				,   f.name   )
						A								=				XLMRobertaTokenizer(f.name				,   keep_accents=a__   )
						A								=				pickle.dumps(a__   )
					pickle.loads(a__   )

				def      _UpperCAmelCase					(						self   )	->				Tuple:
					if not self.test_rust_tokenizer:
						return

					A								=				self.get_tokenizer()
					A								=				self.get_rust_tokenizer()

					A								=				"""I was born in 92000, and this is falsé."""

					A								=				tokenizer.tokenize(a__   )
					A								=				rust_tokenizer.tokenize(a__   )
					self.assertListEqual(a__				,   a__   )

					A								=				tokenizer.encode(a__				,   add_special_tokens=a__   )
					A								=				rust_tokenizer.encode(a__				,   add_special_tokens=a__   )
					self.assertListEqual(a__				,   a__   )

					A								=				self.get_rust_tokenizer()
					A								=				tokenizer.encode(a__   )
					A								=				rust_tokenizer.encode(a__   )
					self.assertListEqual(a__				,   a__   )

				@slow
				def      _UpperCAmelCase					(						self   )	->				Any:
					A								=				"""Hello World!"""
					A								=				[0, 3_5378, 6661, 38, 2]
					# xlmr = torch.hub.load('pytorch/fairseq', 'xlmr.base')  # xlmr.large has same tokenizer
					# xlmr.eval()
					# xlmr.encode(symbols)

					self.assertListEqual(a__				,   self.big_tokenizer.encode(a__   )   )

				@slow
				def      _UpperCAmelCase					(						self   )	->				Tuple:
					A								=				(
					    """This is a very long text with a lot of weird characters, such as: . , ~ ? ( ) \" [ ] ! : - . Also we will"""
					    """ add words that should not exsist and be tokenized to <unk>, such as saoneuhaoesuth"""
					)
					A								=				[
					    0,
					    3293,
					    83,
					    10,
					    4552,
					    4989,
					    7986,
					    678,
					    10,
					    5915,
					    111,
					    17_9459,
					    12_4850,
					    4,
					    6044,
					    237,
					    12,
					    6,
					    5,
					    6,
					    4,
					    6780,
					    705,
					    15,
					    1388,
					    44,
					    378,
					    1_0114,
					    711,
					    152,
					    20,
					    6,
					    5,
					    2_2376,
					    642,
					    1221,
					    1_5190,
					    3_4153,
					    450,
					    5608,
					    959,
					    1119,
					    5_7702,
					    136,
					    186,
					    47,
					    1098,
					    2_9367,
					    47,
					    # 4426, # What fairseq tokenizes from "<unk>": "_<"
					    # 3678, # What fairseq tokenizes from "<unk>": "unk"
					    # 2740, # What fairseq tokenizes from "<unk>": ">"
					    3,  # What we tokenize from "<unk>": "<unk>"
					    6,  # Residue from the tokenization: an extra sentencepiece underline
					    4,
					    6044,
					    237,
					    6284,
					    5_0901,
					    528,
					    31,
					    90,
					    34,
					    927,
					    2,
					]
					# xlmr = torch.hub.load('pytorch/fairseq', 'xlmr.base')  # xlmr.large has same tokenizer
					# xlmr.eval()
					# xlmr.encode(symbols)

					self.assertListEqual(a__				,   self.big_tokenizer.encode(a__   )   )

				@slow
				def      _UpperCAmelCase					(						self   )	->				Union[str, Any]:
					# fmt: off
					A								=				{"""input_ids""": [[0, 1_1062, 8_2772, 7, 15, 8_2772, 538, 5_1529, 237, 1_7198, 1290, 206, 9, 21_5175, 1314, 136, 1_7198, 1290, 206, 9, 5_6359, 42, 12_2009, 9, 1_6466, 16, 8_7344, 4537, 9, 4717, 7_8381, 6, 15_9958, 7, 15, 2_4480, 618, 4, 527, 2_2693, 5428, 4, 2777, 2_4480, 9874, 4, 4_3523, 594, 4, 803, 1_8392, 3_3189, 18, 4, 4_3523, 2_4447, 1_2399, 100, 2_4955, 8_3658, 9626, 14_4057, 15, 839, 2_2335, 16, 136, 2_4955, 8_3658, 8_3479, 15, 3_9102, 724, 16, 678, 645, 2789, 1328, 4589, 42, 12_2009, 11_5774, 23, 805, 1328, 4_6876, 7, 136, 5_3894, 1940, 4_2227, 4_1159, 1_7721, 823, 425, 4, 2_7512, 9_8722, 206, 136, 5531, 4970, 919, 1_7336, 5, 2], [0, 2_0080, 618, 83, 8_2775, 47, 479, 9, 1517, 73, 5_3894, 333, 8_0581, 11_0117, 1_8811, 5256, 1295, 51, 15_2526, 297, 7986, 390, 12_4416, 538, 3_5431, 214, 98, 1_5044, 2_5737, 136, 7108, 4_3701, 23, 756, 13_5355, 7, 5, 2, 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, 581, 6_3773, 11_9455, 6, 14_7797, 8_8203, 7, 645, 70, 21, 3285, 1_0269, 5, 2, 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]], """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, 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, 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=a__				,   model_name="""xlm-roberta-base"""				,   revision="""d9d8a8ea5eb94b1c6654ae9249df7793cd2933d3"""				,   )







import sys
from collections import defaultdict






class       _UpperCamelCase    :

				"""simple docstring"""







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

				def      _UpperCAmelCase					(						self				,   a__   )	->				List[str]:
					return self.node_position[vertex]

				def      _UpperCAmelCase					(						self				,   a__				,   a__   )	->				Optional[int]:
					A								=				pos

				def      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__   )	->				Any:
					if start > size // 2 - 1:
						return
					else:
						if 2 * start + 2 >= size:
							A								=				2 * start + 1
						else:
							if heap[2 * start + 1] < heap[2 * start + 2]:
								A								=				2 * start + 1
							else:
								A								=				2 * start + 2
						if heap[smallest_child] < heap[start]:
							A					,			A								=				heap[smallest_child], positions[smallest_child]
							A					,			A								=				(
							    heap[start],
							    positions[start],
							)
							A					,			A								=				temp, tempa

							A								=				self.get_position(positions[smallest_child]   )
							self.set_position(
							    positions[smallest_child]				,   self.get_position(positions[start]   )   )
							self.set_position(positions[start]				,   a__   )

							self.top_to_bottom(a__				,   a__				,   a__				,   a__   )

				def      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__   )	->				Dict:
					A								=				position[index]

					while index != 0:
						A								=				int((index - 2) / 2   ) if index % 2 == 0 else int((index - 1) / 2   )

						if val < heap[parent]:
							A								=				heap[parent]
							A								=				position[parent]
							self.set_position(position[parent]				,   a__   )
						else:
							A								=				val
							A								=				temp
							self.set_position(a__				,   a__   )
							break
						A								=				parent
					else:
						A								=				val
						A								=				temp
						self.set_position(a__				,   0   )

				def      _UpperCAmelCase					(						self				,   a__				,   a__   )	->				Optional[int]:
					A								=				len(a__   ) // 2 - 1
					for i in range(a__				,   -1				,   -1   ):
						self.top_to_bottom(a__				,   a__				,   len(a__   )				,   a__   )

				def      _UpperCAmelCase					(						self				,   a__				,   a__   )	->				Any:
					A								=				positions[0]
					A								=				sys.maxsize
					self.top_to_bottom(a__				,   0				,   len(a__   )				,   a__   )
					return temp





def   _lowerCAmelCase				(   UpperCamelCase__:     List[str]						) ->   List[str]:





	"""simple docstring"""







	A								=				Heap()

	A								=				[0] * len(UpperCamelCase__						)
	A								=				[-1] * len(UpperCamelCase__						)  # Neighboring Tree Vertex of selected vertex
	# Minimum Distance of explored vertex with neighboring vertex of partial tree
	# formed in graph
	A								=				[]  # Heap of Distance of vertices from their neighboring vertex
	A								=				[]

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

	A								=				[]
	A								=				1
	A								=				sys.maxsize
	for neighbor, distance in adjacency_list[0]:
		A								=				0
		A								=				distance
	heap.heapify(UpperCamelCase__							,					UpperCamelCase__						)

	for _ in range(1							,					len(UpperCamelCase__						)						):
		A								=				heap.delete_minimum(UpperCamelCase__							,					UpperCamelCase__						)
		if visited[vertex] == 0:
			tree_edges.append((nbr_tv[vertex], vertex)						)
			A								=				1
			for neighbor, distance in adjacency_list[vertex]:
				if (
				    visited[neighbor] == 0
				    and distance < distance_tv[heap.get_position(UpperCamelCase__						)]
				):
					A								=				distance
					heap.bottom_to_top(
					    UpperCamelCase__							,					heap.get_position(UpperCamelCase__						)							,					UpperCamelCase__							,					UpperCamelCase__						)
					A								=				vertex
	return tree_edges


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



