'''simple docstring'''





import unittest

from transformers import DebertaVaTokenizer, DebertaVaTokenizerFast
from transformers.testing_utils import get_tests_dir, require_sentencepiece, require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin


lowerCAmelCase_	:		Tuple			=     get_tests_dir("""fixtures/spiece.model""")




@require_sentencepiece
@require_tokenizers
class 		SCREAMING_SNAKE_CASE     (					SCREAMING_SNAKE_CASE   , unittest.TestCase	):







				'''simple docstring'''
				UpperCAmelCase__							=							DebertaVaTokenizer
				UpperCAmelCase__							=							DebertaVaTokenizerFast
				UpperCAmelCase__							=							True
				UpperCAmelCase__							=							True





				def  snake_case__				(						self					:						Dict					)							->List[Any]:


										'''simple docstring'''




										super().setUp()

										# We have a SentencePiece fixture for testing
										_UpperCamelCase			:			Any   			=						DebertaVaTokenizer(lowercase__       ,		unk_token="<unk>"					)
										tokenizer.save_pretrained(self.tmpdirname					)





				def  snake_case__				(						self					:						str       ,		lowercase__					:						Optional[int]					)							->List[Any]:


										'''simple docstring'''




										_UpperCamelCase			:			List[Any]   			=						"this is a test"
										_UpperCamelCase			:			List[Any]   			=						"this is a test"
										return input_text, output_text





				def  snake_case__				(						self					:						Tuple					)							->List[Any]:


										'''simple docstring'''




										_UpperCamelCase			:			Tuple   			=						"<pad>"
										_UpperCamelCase			:			Optional[Any]   			=						0

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





				def  snake_case__				(						self					:						Optional[int]					)							->Tuple:


										'''simple docstring'''




										_UpperCamelCase			:			int   			=						list(self.get_tokenizer().get_vocab().keys()					)
										self.assertEqual(vocab_keys[0]       ,		"<pad>"					)
										self.assertEqual(vocab_keys[1]       ,		"<unk>"					)
										self.assertEqual(vocab_keys[-1]       ,		"[PAD]"					)
										self.assertEqual(len(lowercase__					)       ,		30_001					)





				def  snake_case__				(						self					:						int					)							->Tuple:


										'''simple docstring'''




										self.assertEqual(self.get_tokenizer().vocab_size       ,		30_000					)





				def  snake_case__				(						self					:						List[Any]					)							->Dict:


										'''simple docstring'''




										_UpperCamelCase			:			int   			=						" \tHeLLo!how  \n Are yoU?  "
										_UpperCamelCase			:			List[str]   			=						["▁hello", "!", "how", "▁are", "▁you", "?"]
										# fmt: on

										_UpperCamelCase			:			Optional[Any]   			=						DebertaVaTokenizer(lowercase__       ,		do_lower_case=lowercase__					)
										_UpperCamelCase			:			Optional[int]   			=						tokenizer.convert_ids_to_tokens(tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Optional[int]   			=						DebertaVaTokenizerFast(lowercase__       ,		do_lower_case=lowercase__					)
										_UpperCamelCase			:			List[Any]   			=						rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)





				@unittest.skip("There is an inconsistency between slow and fast tokenizer due to a bug in the fast one."					)
				def  snake_case__				(						self					:						Optional[Any]					)							->Dict:


										'''simple docstring'''




										pass





				@unittest.skip("There is an inconsistency between slow and fast tokenizer due to a bug in the fast one."					)
				def  snake_case__				(						self					:						Tuple					)							->str:


										'''simple docstring'''




										pass





				def  snake_case__				(						self					:						Dict					)							->Optional[Any]:


										'''simple docstring'''




										_UpperCamelCase			:			int   			=						"I was born in 92000, and this is falsé."
										_UpperCamelCase			:			int   			=						["▁", "<unk>", "▁was", "▁born", "▁in", "▁9", "2000", "▁", ",", "▁and", "▁this", "▁is", "▁fal", "s", "<unk>", "▁", ".", ]
										# fmt: on

										_UpperCamelCase			:			Union[str, Any]   			=						DebertaVaTokenizer(lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			Any   			=						tokenizer.convert_ids_to_tokens(tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Any   			=						DebertaVaTokenizerFast(lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			Any   			=						rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						List[Any]					)							->List[str]:


										'''simple docstring'''




										_UpperCamelCase			:			Tuple   			=						"I was born in 92000, and this is falsé."
										_UpperCamelCase			:			List[str]   			=						["▁i", "▁was", "▁born", "▁in", "▁9", "2000", "▁", ",", "▁and", "▁this", "▁is", "▁fal", "s", "<unk>", "▁", ".", ]
										# fmt: on

										_UpperCamelCase			:			Optional[int]   			=						DebertaVaTokenizer(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			Optional[Any]   			=						tokenizer.convert_ids_to_tokens(tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)
										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Union[str, Any]   			=						DebertaVaTokenizerFast(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			Optional[Any]   			=						rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)
										self.assertListEqual(lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						Optional[int]					)							->Dict:


										'''simple docstring'''




										_UpperCamelCase			:			Tuple   			=						"I was born in 92000, and this is falsé."
										_UpperCamelCase			:			Optional[Any]   			=						["▁i", "▁was", "▁born", "▁in", "▁9", "2000", ",", "▁and", "▁this", "▁is", "▁fal", "s", "<unk>", ".", ]
										# fmt: on

										_UpperCamelCase			:			Optional[Any]   			=						DebertaVaTokenizer(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			Dict   			=						tokenizer.convert_ids_to_tokens(tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Dict   			=						DebertaVaTokenizerFast(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			int   			=						rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						int					)							->Any:


										'''simple docstring'''




										_UpperCamelCase			:			Tuple   			=						"I was born in 92000, and this is falsé."
										_UpperCamelCase			:			Optional[Any]   			=						["▁", "<unk>", "▁was", "▁born", "▁in", "▁9", "2000", "▁", ",", "▁and", "▁this", "▁is", "▁fal", "s", "<unk>", "▁", ".", ]
										# fmt: on

										_UpperCamelCase			:			Union[str, Any]   			=						DebertaVaTokenizer(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			List[str]   			=						tokenizer.convert_ids_to_tokens(tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Dict   			=						DebertaVaTokenizerFast(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			Union[str, Any]   			=						rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						Optional[int]					)							->str:


										'''simple docstring'''




										_UpperCamelCase			:			str   			=						" \tHeLLo!how  \n Are yoU?  "
										_UpperCamelCase			:			List[str]   			=						["▁", "<unk>", "e", "<unk>", "o", "!", "how", "▁", "<unk>", "re", "▁yo", "<unk>", "?"]
										# fmt: on

										_UpperCamelCase			:			Optional[int]   			=						DebertaVaTokenizer(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			int   			=						tokenizer.convert_ids_to_tokens(tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			str   			=						DebertaVaTokenizerFast(lowercase__       ,		do_lower_case=lowercase__       ,		split_by_punct=lowercase__					)
										_UpperCamelCase			:			Optional[int]   			=						rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)

										self.assertListEqual(lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						List[str]					)							->Optional[int]:


										'''simple docstring'''




										_UpperCamelCase			:			List[Any]   			=						self.get_tokenizer()
										_UpperCamelCase			:			List[str]   			=						self.get_rust_tokenizer()

										_UpperCamelCase			:			int   			=						"I was born in 92000, and this is falsé."

										_UpperCamelCase			:			List[Any]   			=						tokenizer.convert_ids_to_tokens(tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)
										_UpperCamelCase			:			Union[str, Any]   			=						rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)					)
										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Union[str, Any]   			=						tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)
										_UpperCamelCase			:			int   			=						rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Dict   			=						self.get_rust_tokenizer()
										_UpperCamelCase			:			List[str]   			=						tokenizer.encode(lowercase__					)
										_UpperCamelCase			:			List[Any]   			=						rust_tokenizer.encode(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						List[Any]					)							->Any:


										'''simple docstring'''




										_UpperCamelCase			:			Tuple   			=						"This is a test"
										_UpperCamelCase			:			Optional[Any]   			=						[13, 1, 4_398, 25, 21, 1_289]
										_UpperCamelCase			:			List[str]   			=						["▁", "T", "his", "▁is", "▁a", "▁test"]
										_UpperCamelCase			:			Optional[Any]   			=						["▁", "<unk>", "his", "▁is", "▁a", "▁test"]

										_UpperCamelCase			:			Tuple   			=						DebertaVaTokenizer(lowercase__       ,		keep_accents=lowercase__					)
										_UpperCamelCase			:			Dict   			=						DebertaVaTokenizerFast(lowercase__       ,		keep_accents=lowercase__					)

										_UpperCamelCase			:			Optional[int]   			=						tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			Optional[Any]   			=						tokenizer.tokenize(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			Optional[int]   			=						tokenizer.convert_ids_to_tokens(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			str   			=						rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			Optional[int]   			=						rust_tokenizer.tokenize(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			Any   			=						rust_tokenizer.convert_ids_to_tokens(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)

										# fmt: off
										_UpperCamelCase			:			Any   			=						"I was born in 92000, and this is falsé."
										_UpperCamelCase			:			Dict   			=						[13, 1, 23, 386, 19, 561, 3_050, 15, 17, 48, 25, 8_256, 18, 1, 9]
										_UpperCamelCase			:			List[Any]   			=						["▁", "I", "▁was", "▁born", "▁in", "▁9", "2000", ",", "▁and", "▁this", "▁is", "▁fal", "s", "é", ".", ]
										_UpperCamelCase			:			List[str]   			=						["▁", "<unk>", "▁was", "▁born", "▁in", "▁9", "2000", ",", "▁and", "▁this", "▁is", "▁fal", "s", "<unk>", ".", ]
										# fmt: on

										_UpperCamelCase			:			Dict   			=						tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			int   			=						tokenizer.tokenize(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			Optional[int]   			=						tokenizer.convert_ids_to_tokens(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)

										_UpperCamelCase			:			Union[str, Any]   			=						rust_tokenizer.encode(lowercase__       ,		add_special_tokens=lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			List[Any]   			=						rust_tokenizer.tokenize(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)
										_UpperCamelCase			:			List[Any]   			=						rust_tokenizer.convert_ids_to_tokens(lowercase__					)
										self.assertListEqual(lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						int					)							->Any:


										'''simple docstring'''




										_UpperCamelCase			:			int   			=						DebertaVaTokenizer(lowercase__					)

										_UpperCamelCase			:			str   			=						tokenizer.encode("sequence builders"					)
										_UpperCamelCase			:			int   			=						tokenizer.encode("multi-sequence build"					)

										_UpperCamelCase			:			str   			=						tokenizer.build_inputs_with_special_tokens(lowercase__					)
										_UpperCamelCase			:			Optional[int]   			=						tokenizer.build_inputs_with_special_tokens(lowercase__       ,		lowercase__					)

										self.assertEqual([tokenizer.cls_token_id] + text + [tokenizer.sep_token_id]       ,		lowercase__					)
										self.assertEqual(
										    [tokenizer.cls_token_id] + text + [tokenizer.sep_token_id] + text_a + [tokenizer.sep_token_id]       ,		lowercase__       ,		)







				@slow
				def  snake_case__				(						self					:						List[Any]					)							->Optional[int]:


										'''simple docstring'''




										_UpperCamelCase			:			str   			=						{"input_ids": [[1, 39_867, 36, 19_390, 486, 27, 35_052, 81_436, 18, 60_685, 1_225, 7, 35_052, 81_436, 18, 9_367, 16_899, 18, 15_937, 53, 594, 773, 18, 16_287, 30_465, 36, 15_937, 6, 41_139, 38, 36_979, 60_763, 191, 6, 34_132, 99, 6, 50_538, 390, 43_230, 6, 34_132, 2_779, 20_850, 14, 699, 1_072, 1_194, 36, 382, 10_901, 53, 7, 699, 1_072, 2_084, 36, 20_422, 630, 53, 19, 105, 3_049, 1_896, 1_053, 16_899, 1_506, 11, 37_978, 4_243, 7, 1_237, 31_869, 200, 16_566, 654, 6, 35_052, 81_436, 7, 55_630, 13_593, 4, 2], [1, 26, 15_011, 13, 667, 8, 1_053, 18, 23_611, 1_237, 72_356, 12_820, 34, 104_134, 1_209, 35, 13_313, 6_627, 21, 202, 347, 7, 164, 2_399, 11, 46, 4_485, 4, 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], [1, 5, 1_232, 2_864, 15_785, 14_951, 105, 5, 8_581, 1_250, 4, 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]], "token_type_ids": [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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=lowercase__       ,		model_name="microsoft/deberta-v2-xlarge"       ,		revision="ad6e42c1532ddf3a15c39246b63f5559d558b670"       ,		)



'''simple docstring'''





import sys
from collections import defaultdict




class 		SCREAMING_SNAKE_CASE     :







				'''simple docstring'''





				def __init__(						self					:						Tuple					)							->Optional[int]:


										'''simple docstring'''




										_UpperCamelCase			:			List[Any]   			=						[]





				def  snake_case__				(						self					:						Any       ,		lowercase__					:						Any					)							->Optional[int]:


										'''simple docstring'''




										return self.node_position[vertex]





				def  snake_case__				(						self					:						str       ,		lowercase__					:						Optional[int]       ,		lowercase__					:						Optional[int]					)							->int:


										'''simple docstring'''




										_UpperCamelCase			:			List[Any]   			=						pos





				def  snake_case__				(						self					:						Union[str, Any]       ,		lowercase__					:						Optional[int]       ,		lowercase__					:						List[Any]       ,		lowercase__					:						Dict       ,		lowercase__					:						Dict					)							->Dict:


										'''simple docstring'''




										if start > size // 2 - 1:
																return
										else:
																if 2 * start + 2 >= size:
																						_UpperCamelCase			:			Tuple   			=						2 * start + 1
																else:
																						if heap[2 * start + 1] < heap[2 * start + 2]:
																												_UpperCamelCase			:			str   			=						2 * start + 1
																						else:
																												_UpperCamelCase			:			List[Any]   			=						2 * start + 2
																if heap[smallest_child] < heap[start]:
																						_UpperCamelCase			,       _UpperCamelCase			:			Dict   			=						heap[smallest_child], positions[smallest_child]
																						_UpperCamelCase			,       _UpperCamelCase			:			int   			=						(
																						    heap[start],
																						    positions[start],
																						)
																						_UpperCamelCase			,       _UpperCamelCase			:			Tuple   			=						temp, tempa

																						_UpperCamelCase			:			Optional[Any]   			=						self.get_position(positions[smallest_child]					)
																						self.set_position(
																						    positions[smallest_child]       ,		self.get_position(positions[start]					)					)
																						self.set_position(positions[start]       ,		lowercase__					)

																						self.top_to_bottom(lowercase__       ,		lowercase__       ,		lowercase__       ,		lowercase__					)





				def  snake_case__				(						self					:						Optional[int]       ,		lowercase__					:						List[Any]       ,		lowercase__					:						str       ,		lowercase__					:						List[Any]       ,		lowercase__					:						List[str]					)							->str:


										'''simple docstring'''




										_UpperCamelCase			:			str   			=						position[index]

										while index != 0:
																_UpperCamelCase			:			List[str]   			=						int((index - 2) / 2					) if index % 2 == 0 else int((index - 1) / 2					)

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





				def  snake_case__				(						self					:						Tuple       ,		lowercase__					:						Optional[Any]       ,		lowercase__					:						Tuple					)							->Optional[int]:


										'''simple docstring'''




										_UpperCamelCase			:			Optional[int]   			=						len(lowercase__					) // 2 - 1
										for i in range(lowercase__       ,		-1       ,		-1					):
																self.top_to_bottom(lowercase__       ,		lowercase__       ,		len(lowercase__					)       ,		lowercase__					)







				def  snake_case__				(						self					:						Dict       ,		lowercase__					:						Union[str, Any]       ,		lowercase__					:						Union[str, Any]					)							->Any:


										'''simple docstring'''




										_UpperCamelCase			:			List[Any]   			=						positions[0]
										_UpperCamelCase			:			Tuple   			=						sys.maxsize
										self.top_to_bottom(lowercase__       ,		0       ,		len(lowercase__					)       ,		lowercase__					)
										return temp





def 						__A							(     UpperCAmelCase					)     ->			Any:




						'''simple docstring'''
						_UpperCamelCase			:			Union[str, Any]   			=						Heap()

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

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

						_UpperCamelCase			:			Optional[Any]   			=						[]
						_UpperCamelCase			:			Union[str, Any]   			=						1
						_UpperCamelCase			:			int   			=						sys.maxsize
						for neighbor, distance in adjacency_list[0]:
												_UpperCamelCase			:			Union[str, Any]   			=						0
												_UpperCamelCase			:			int   			=						distance
						heap.heapify(UpperCAmelCase     ,UpperCAmelCase					)

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


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


