


"""simple docstring"""


import json
import os
import re
import shutil
import tempfile
import unittest
from typing import Tuple

from transformers import AddedToken, BatchEncoding, PerceiverTokenizer
from transformers.utils import cached_property, is_tf_available, is_torch_available

from ...test_tokenization_common import TokenizerTesterMixin


if is_torch_available():
	A     :   Union[str, Any]			    =			"pt"
elif is_tf_available():
	A     :   Optional[Any]			    =			"tf"
else:
	A     :   Any			    =			"jax"
class   _UpperCamelCase  (   lowerCAmelCase__       ,unittest.TestCase		):
							'''simple docstring'''







							__UpperCAmelCase						:    str				      =PerceiverTokenizer
							__UpperCAmelCase						:    List[str]				      =False

							def 			snake_case				(     self	):
										super().setUp()
										__lowerCAmelCase				    =			PerceiverTokenizer()
										tokenizer.save_pretrained(self.tmpdirname	)

							@cached_property
							def 			snake_case				(     self	):
										return PerceiverTokenizer.from_pretrained("deepmind/language-perceiver"	)

							def 			snake_case				(     self    ,   **__a	):
										return self.tokenizer_class.from_pretrained(self.tmpdirname    ,   **__a	)

							def 			snake_case				(     self    ,   __a    ,   __a=False    ,   __a=20    ,   __a=5	):
										# XXX The default common tokenizer tests assume that every ID is decodable on its own.
										# This assumption is invalid for Perceiver because single bytes might not be
										# valid utf-8 (byte 128 for instance).
										# Here we're overriding the smallest possible method to provide
										# a clean sequence without making the same assumption.

										__lowerCAmelCase				    =			[]
										for i in range(len(__a	)	):
													try:
																__lowerCAmelCase				    =			tokenizer.decode([i]    ,   clean_up_tokenization_spaces=__a	)
													except UnicodeDecodeError:
																pass
													toks.append((i, tok)	)

										__lowerCAmelCase				    =			list(filter(lambda __a	: re.match(R"^[ a-zA-Z]+$"    ,   t[1]	)    ,   __a	)	)
										__lowerCAmelCase				    =			list(filter(lambda __a	: [t[0]] == tokenizer.encode(t[1]    ,   add_special_tokens=__a	)    ,   __a	)	)
										if max_length is not None and len(__a	) > max_length:
													__lowerCAmelCase				    =			toks[:max_length]
										if min_length is not None and len(__a	) < min_length and len(__a	) > 0:
													while len(__a	) < min_length:
																__lowerCAmelCase				    =			toks + toks
        # toks_str = [t[1] for t in toks]
										__lowerCAmelCase				    =			[t[0] for t in toks]

										# Ensure consistency
										__lowerCAmelCase				    =			tokenizer.decode(__a    ,   clean_up_tokenization_spaces=__a	)
										if " " not in output_txt and len(__a	) > 1:
													__lowerCAmelCase				    =			(
													    tokenizer.decode([toks_ids[0]]    ,   clean_up_tokenization_spaces=__a	)
													    + " "
													    + tokenizer.decode(toks_ids[1:]    ,   clean_up_tokenization_spaces=__a	)
													)
										if with_prefix_space:
													__lowerCAmelCase				    =			" " + output_txt
										__lowerCAmelCase				    =			tokenizer.encode(__a    ,   add_special_tokens=__a	)
										return output_txt, output_ids

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.perceiver_tokenizer
										__lowerCAmelCase				    =			"Unicode €."
										__lowerCAmelCase				    =			tokenizer(__a	)
										__lowerCAmelCase				    =			[4, 91, 1_16, 1_11, 1_05, 1_17, 1_06, 1_07, 38, 2_32, 1_36, 1_78, 52, 5]
										self.assertEqual(encoded["input_ids"]    ,   __a	)

										# decoding
										__lowerCAmelCase				    =			tokenizer.decode(__a	)
										self.assertEqual(__a    ,   "[CLS]Unicode €.[SEP]"	)

										__lowerCAmelCase				    =			tokenizer("e è é ê ë"	)
										__lowerCAmelCase				    =			[4, 1_07, 38, 2_01, 1_74, 38, 2_01, 1_75, 38, 2_01, 1_76, 38, 2_01, 1_77, 5]
										self.assertEqual(encoded["input_ids"]    ,   __a	)
										# decoding
										__lowerCAmelCase				    =			tokenizer.decode(__a	)
										self.assertEqual(__a    ,   "[CLS]e è é ê ë[SEP]"	)

										# encode/decode, but with `encode` instead of `__call__`
										self.assertEqual(tokenizer.decode(tokenizer.encode("e è é ê ë"	)	)    ,   "[CLS]e è é ê ë[SEP]"	)

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.perceiver_tokenizer
										__lowerCAmelCase				    =			["A long paragraph for summarization.", "Another paragraph for summarization."]
										# fmt: off
										__lowerCAmelCase				    =			[4, 71, 38, 1_14, 1_17, 1_16, 1_09, 38, 1_18, 1_03, 1_20, 1_03, 1_09, 1_20, 1_03, 1_18, 1_10, 38, 1_08, 1_17, 1_20, 38, 1_21, 1_23, 1_15, 1_15, 1_03, 1_20, 1_11, 1_28, 1_03, 1_22, 1_11, 1_17, 1_16, 52, 5, 0]
										# fmt: on
										__lowerCAmelCase				    =			tokenizer(__a    ,   padding=__a    ,   return_tensors=__a	)
										self.assertIsInstance(__a    ,   __a	)

										if FRAMEWORK != "jax":
													__lowerCAmelCase				    =			list(batch.input_ids.numpy()[0]	)
										else:
													__lowerCAmelCase				    =			list(batch.input_ids.tolist()[0]	)

										self.assertListEqual(__a    ,   __a	)

										self.assertEqual((2, 38)    ,   batch.input_ids.shape	)
										self.assertEqual((2, 38)    ,   batch.attention_mask.shape	)

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.perceiver_tokenizer
										__lowerCAmelCase				    =			["A long paragraph for summarization.", "Another paragraph for summarization."]
										__lowerCAmelCase				    =			tokenizer(__a    ,   padding=__a    ,   return_tensors=__a	)
										# check if input_ids are returned and no decoder_input_ids
										self.assertIn("input_ids"    ,   __a	)
										self.assertIn("attention_mask"    ,   __a	)
										self.assertNotIn("decoder_input_ids"    ,   __a	)
										self.assertNotIn("decoder_attention_mask"    ,   __a	)

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.perceiver_tokenizer
										__lowerCAmelCase				    =			[
										    "Summary of the text.",
										    "Another summary.",
										]
										__lowerCAmelCase				    =			tokenizer(
										    text_target=__a    ,   max_length=32    ,   padding="max_length"    ,   truncation=__a    ,   return_tensors=__a	)
										self.assertEqual(32    ,   targets["input_ids"].shape[1]	)

							def 			snake_case				(     self	):
										# safety check on max_len default value so we are sure the test works
										__lowerCAmelCase				    =			self.get_tokenizers()
										for tokenizer in tokenizers:
													with self.subTest(f"{tokenizer.__class__.__name__}"	):
																self.assertNotEqual(tokenizer.model_max_length    ,   42	)

        # Now let's start the test
										__lowerCAmelCase				    =			self.get_tokenizers()
										for tokenizer in tokenizers:
													with self.subTest(f"{tokenizer.__class__.__name__}"	):
																# Isolate this from the other tests because we save additional tokens/etc
																__lowerCAmelCase				    =			tempfile.mkdtemp()

																__lowerCAmelCase				    =			" He is very happy, UNwant\u00E9d,running"
																__lowerCAmelCase				    =			tokenizer.encode(__a    ,   add_special_tokens=__a	)
																tokenizer.save_pretrained(__a	)

																__lowerCAmelCase				    =			tokenizer.__class__.from_pretrained(__a	)
																__lowerCAmelCase				    =			after_tokenizer.encode(__a    ,   add_special_tokens=__a	)
																self.assertListEqual(__a    ,   __a	)

																shutil.rmtree(__a	)

										__lowerCAmelCase				    =			self.get_tokenizers(model_max_length=42	)
										for tokenizer in tokenizers:
													with self.subTest(f"{tokenizer.__class__.__name__}"	):
																# Isolate this from the other tests because we save additional tokens/etc
																__lowerCAmelCase				    =			tempfile.mkdtemp()

																__lowerCAmelCase				    =			" He is very happy, UNwant\u00E9d,running"
																tokenizer.add_tokens(["bim", "bambam"]	)
																__lowerCAmelCase				    =			tokenizer.additional_special_tokens
																additional_special_tokens.append("new_additional_special_token"	)
																tokenizer.add_special_tokens({"additional_special_tokens": additional_special_tokens}	)
																__lowerCAmelCase				    =			tokenizer.encode(__a    ,   add_special_tokens=__a	)
																tokenizer.save_pretrained(__a	)

																__lowerCAmelCase				    =			tokenizer.__class__.from_pretrained(__a	)
																__lowerCAmelCase				    =			after_tokenizer.encode(__a    ,   add_special_tokens=__a	)
																self.assertListEqual(__a    ,   __a	)
																self.assertIn("new_additional_special_token"    ,   after_tokenizer.additional_special_tokens	)
																self.assertEqual(after_tokenizer.model_max_length    ,   42	)

																__lowerCAmelCase				    =			tokenizer.__class__.from_pretrained(__a    ,   model_max_length=43	)
																self.assertEqual(tokenizer.model_max_length    ,   43	)

																shutil.rmtree(__a	)

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			[]
										if self.test_slow_tokenizer:
													tokenizer_list.append((self.tokenizer_class, self.get_tokenizer())	)

										if self.test_rust_tokenizer:
													tokenizer_list.append((self.rust_tokenizer_class, self.get_rust_tokenizer())	)

										for tokenizer_class, tokenizer_utils in tokenizer_list:
													with tempfile.TemporaryDirectory() as tmp_dir:
																tokenizer_utils.save_pretrained(__a	)

																with open(os.path.join(__a    ,   "special_tokens_map.json"	)    ,   encoding="utf-8"	) as json_file:
																			__lowerCAmelCase				    =			json.load(__a	)

																with open(os.path.join(__a    ,   "tokenizer_config.json"	)    ,   encoding="utf-8"	) as json_file:
																			__lowerCAmelCase				    =			json.load(__a	)

																__lowerCAmelCase				    =			[f"<extra_id_{i}>" for i in range(1_25	)]

																__lowerCAmelCase				    =			added_tokens_extra_ids + [
																    "an_additional_special_token"
																]
																__lowerCAmelCase				    =			added_tokens_extra_ids + [
																    "an_additional_special_token"
																]

																with open(os.path.join(__a    ,   "special_tokens_map.json"	)    ,   "w"    ,   encoding="utf-8"	) as outfile:
																			json.dump(__a    ,   __a	)
																with open(os.path.join(__a    ,   "tokenizer_config.json"	)    ,   "w"    ,   encoding="utf-8"	) as outfile:
																			json.dump(__a    ,   __a	)

																# the following checks allow us to verify that our test works as expected, i.e. that the tokenizer takes
																# into account the new value of additional_special_tokens given in the "tokenizer_config.json" and
																# "special_tokens_map.json" files
																__lowerCAmelCase				    =			tokenizer_class.from_pretrained(
																    __a    ,   )
																self.assertIn(
																    "an_additional_special_token"    ,   tokenizer_without_change_in_init.additional_special_tokens	)
																self.assertEqual(
																    ["an_additional_special_token"]    ,   tokenizer_without_change_in_init.convert_ids_to_tokens(
																        tokenizer_without_change_in_init.convert_tokens_to_ids(["an_additional_special_token"]	)	)    ,   )

																# Now we test that we can change the value of additional_special_tokens in the from_pretrained
																__lowerCAmelCase				    =			added_tokens_extra_ids + [AddedToken("a_new_additional_special_token"    ,   lstrip=__a	)]
																__lowerCAmelCase				    =			tokenizer_class.from_pretrained(
																    __a    ,   additional_special_tokens=__a    ,   )

																self.assertIn("a_new_additional_special_token"    ,   tokenizer.additional_special_tokens	)
																self.assertEqual(
																    ["a_new_additional_special_token"]    ,   tokenizer.convert_ids_to_tokens(
																        tokenizer.convert_tokens_to_ids(["a_new_additional_special_token"]	)	)    ,   )

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.perceiver_tokenizer
										self.assertEqual(tokenizer.decode([1_78]	)    ,   "�"	)

							def 			snake_case				(     self	):
										pass

							def 			snake_case				(     self	):
										pass

							def 			snake_case				(     self	):
										pass

							def 			snake_case				(     self	):
										pass



							def 			snake_case				(     self	):
										# The default common tokenizer tests uses invalid tokens for Perceiver that can only accept one-character
										# strings and special added tokens as tokens
										__lowerCAmelCase				    =			self.get_tokenizers(fast=__a    ,   do_lower_case=__a	)
										for tokenizer in tokenizers:
													with self.subTest(f"{tokenizer.__class__.__name__}"	):
																__lowerCAmelCase				    =			["[CLS]", "t", "h", "i", "s", " ", "i", "s", " ", "a", " ", "t", "e", "s", "t", "[SEP]"]
																__lowerCAmelCase				    =			tokenizer.convert_tokens_to_string(__a	)

																self.assertIsInstance(__a    ,   __a	)








"""simple docstring"""


import sys
from collections import defaultdict
class   _UpperCamelCase  :
							'''simple docstring'''







							def __init__(     self	):
										__lowerCAmelCase				    =			[]

							def 			snake_case				(     self    ,   __a	):
										return self.node_position[vertex]

							def 			snake_case				(     self    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			pos

							def 			snake_case				(     self    ,   __a    ,   __a    ,   __a    ,   __a	):
										if start > size // 2 - 1:
													return
										else:
													if 2 * start + 2 >= size:
																__lowerCAmelCase				    =			2 * start + 1
													else:
																if heap[2 * start + 1] < heap[2 * start + 2]:
																			__lowerCAmelCase				    =			2 * start + 1
																else:
																			__lowerCAmelCase				    =			2 * start + 2
													if heap[smallest_child] < heap[start]:
																__lowerCAmelCase    ,	__lowerCAmelCase				    =			heap[smallest_child], positions[smallest_child]
																__lowerCAmelCase    ,	__lowerCAmelCase				    =			(
																    heap[start],
																    positions[start],
																)
																__lowerCAmelCase    ,	__lowerCAmelCase				    =			temp, tempa

																__lowerCAmelCase				    =			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 			snake_case				(     self    ,   __a    ,   __a    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			position[index]

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

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

							def 			snake_case				(     self    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			len(__a	) // 2 - 1
										for i in range(__a    ,   -1    ,   -1	):
													self.top_to_bottom(__a    ,   __a    ,   len(__a	)    ,   __a	)



							def 			snake_case				(     self    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			positions[0]
										__lowerCAmelCase				    =			sys.maxsize
										self.top_to_bottom(__a    ,   0    ,   len(__a	)    ,   __a	)
										return temp


def _lowerCamelCase	(		_UpperCamelCase      ):

			'''simple docstring'''




			__lowerCAmelCase				    =			Heap()

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

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

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

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


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




