
"""simple docstring"""


import json
import os
import unittest

from transformers import AutoTokenizer, GPTaTokenizer, GPTaTokenizerFast
from transformers.models.gpta.tokenization_gpta import VOCAB_FILES_NAMES
from transformers.testing_utils import require_tokenizers

from ...test_tokenization_common import TokenizerTesterMixin







@require_tokenizers
class 				lowerCAmelCase_				(      _lowercase		,					unittest.TestCase    ):



						'''simple docstring'''


						_lowerCamelCase:    Tuple      =    GPTaTokenizer
						_lowerCamelCase:    int      =    GPTaTokenizerFast
						_lowerCamelCase:    Dict      =    True
						_lowerCamelCase:    Optional[int]      =    {'''add_prefix_space''': True}
						_lowerCamelCase:    Tuple      =    False


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   int:
							super().setUp()

							# Adapted from Sennrich et al. 2015 and https://github.com/rsennrich/subword-nmt
							A						   =   [
							    'l',
							    'o',
							    'w',
							    'e',
							    'r',
							    's',
							    't',
							    'i',
							    'd',
							    'n',
							    '\u0120',
							    '\u0120l',
							    '\u0120n',
							    '\u0120lo',
							    '\u0120low',
							    'er',
							    '\u0120lowest',
							    '\u0120newer',
							    '\u0120wider',
							    '<unk>',
							    '<|endoftext|>',
							]
							A						   =   dict(zip(A_  ,range(len(A_      )      )      )      )
							A						   =   ['#version: 0.2', '\u0120 l', '\u0120l o', '\u0120lo w', 'e r', '']
							A						   =   {'unk_token': '<unk>'}

							A						   =   os.path.join(self.tmpdirname  ,VOCAB_FILES_NAMES['vocab_file']      )
							A						   =   os.path.join(self.tmpdirname  ,VOCAB_FILES_NAMES['merges_file']      )
							with open(self.vocab_file  ,'w'  ,encoding='utf-8'      ) as fp:
								fp.write(json.dumps(A_      ) + '\n'      )
							with open(self.merges_file  ,'w'  ,encoding='utf-8'      ) as fp:
								fp.write('\n'.join(A_      )      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,**A_     :      int      )     ->   Dict:
							kwargs.update(self.special_tokens_map      )
							return GPTaTokenizer.from_pretrained(self.tmpdirname  ,**A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int  ,**A_     :      Any      )     ->   Optional[int]:
							kwargs.update(self.special_tokens_map      )
							return GPTaTokenizerFast.from_pretrained(self.tmpdirname  ,**A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      int      )     ->   int:
							A						   =   'lower newer'
							A						   =   'lower newer'
							return input_text, output_text


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							A						   =   GPTaTokenizer(self.vocab_file  ,self.merges_file  ,**self.special_tokens_map      )
							A						   =   'lower newer'
							A						   =   ['\u0120low', 'er', '\u0120', 'n', 'e', 'w', 'er']
							A						   =   tokenizer.tokenize(A_  ,add_prefix_space=A_      )
							self.assertListEqual(A_  ,A_      )

							A						   =   tokens + [tokenizer.unk_token]
							A						   =   [14, 15, 10, 9, 3, 2, 15, 19]
							self.assertListEqual(tokenizer.convert_tokens_to_ids(A_      )  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   Optional[int]:
							if not self.test_rust_tokenizer:
								return

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

							A						   =   'lower newer'

							# Testing tokenization
							A						   =   tokenizer.tokenize(A_  ,add_prefix_space=A_      )
							A						   =   rust_tokenizer.tokenize(A_      )
							self.assertListEqual(A_  ,A_      )

							# Testing conversion to ids without special tokens
							A						   =   tokenizer.encode(A_  ,add_special_tokens=A_  ,add_prefix_space=A_      )
							A						   =   rust_tokenizer.encode(A_  ,add_special_tokens=A_      )
							self.assertListEqual(A_  ,A_      )

							# Testing conversion to ids with special tokens
							A						   =   self.get_rust_tokenizer(add_prefix_space=A_      )
							A						   =   tokenizer.encode(A_  ,add_prefix_space=A_      )
							A						   =   rust_tokenizer.encode(A_      )
							self.assertListEqual(A_  ,A_      )

							# Testing the unknown token
							A						   =   tokens + [rust_tokenizer.unk_token]
							A						   =   [14, 15, 10, 9, 3, 2, 15, 19]
							self.assertListEqual(rust_tokenizer.convert_tokens_to_ids(A_      )  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,*A_     :      List[Any]  ,**A_     :      Optional[int]      )     ->   Any:
							# It's very difficult to mix/test pretokenization with byte-level
							# And get both GPT2 and Roberta to work at the same time (mostly an issue of adding a space before the string)
							pass


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Optional[int]=15      )     ->   int:
							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_      )

									# Simple input
									A						   =   'This is a simple input'
									A						   =   ['This is a simple input 1', 'This is a simple input 2']
									A						   =   ('This is a simple input', 'This is a pair')
									A						   =   [
									    ('This is a simple input 1', 'This is a simple input 2'),
									    ('This is a simple pair 1', 'This is a simple pair 2'),
									]

									# Simple input tests
									self.assertRaises(A_  ,tokenizer_r.encode  ,A_  ,max_length=A_  ,padding='max_length'      )

									# Simple input
									self.assertRaises(A_  ,tokenizer_r.encode_plus  ,A_  ,max_length=A_  ,padding='max_length'      )

									# Simple input
									self.assertRaises(
									    A_  ,tokenizer_r.batch_encode_plus  ,A_  ,max_length=A_  ,padding='max_length'  ,)

									# Pair input
									self.assertRaises(A_  ,tokenizer_r.encode  ,A_  ,max_length=A_  ,padding='max_length'      )

									# Pair input
									self.assertRaises(A_  ,tokenizer_r.encode_plus  ,A_  ,max_length=A_  ,padding='max_length'      )

									# Pair input
									self.assertRaises(
									    A_  ,tokenizer_r.batch_encode_plus  ,A_  ,max_length=A_  ,padding='max_length'  ,)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   Dict:
							A						   =   GPTaTokenizer.from_pretrained(self.tmpdirname  ,pad_token='<pad>'      )

							# Simple input
							A						   =   'This is a simple input'
							A						   =   ['This is a simple input looooooooong', 'This is a simple input']
							A						   =   ('This is a simple input', 'This is a pair')
							A						   =   [
							    ('This is a simple input loooooong', 'This is a simple input'),
							    ('This is a simple pair loooooong', 'This is a simple pair'),
							]

							A						   =   tokenizer.pad_token_id

							A						   =   tokenizer(A_  ,padding='max_length'  ,max_length=30  ,return_tensors='np'      )
							A						   =   tokenizer(A_  ,padding=A_  ,truncate=A_  ,return_tensors='np'      )
							A						   =   tokenizer(*A_  ,padding='max_length'  ,max_length=60  ,return_tensors='np'      )
							A						   =   tokenizer(A_  ,padding=A_  ,truncate=A_  ,return_tensors='np'      )

							# s
							# test single string max_length padding
							self.assertEqual(out_s['input_ids'].shape[-1]  ,30      )
							self.assertTrue(pad_token_id in out_s['input_ids']      )
							self.assertTrue(0 in out_s['attention_mask']      )

							# s2
							# test automatic padding
							self.assertEqual(out_sa['input_ids'].shape[-1]  ,33      )
							# long slice doesn't have padding
							self.assertFalse(pad_token_id in out_sa['input_ids'][0]      )
							self.assertFalse(0 in out_sa['attention_mask'][0]      )
							# short slice does have padding
							self.assertTrue(pad_token_id in out_sa['input_ids'][1]      )
							self.assertTrue(0 in out_sa['attention_mask'][1]      )

							# p
							# test single pair max_length padding
							self.assertEqual(out_p['input_ids'].shape[-1]  ,60      )
							self.assertTrue(pad_token_id in out_p['input_ids']      )
							self.assertTrue(0 in out_p['attention_mask']      )

							# p2
							# test automatic padding pair
							self.assertEqual(out_pa['input_ids'].shape[-1]  ,52      )
							# long slice pair doesn't have padding
							self.assertFalse(pad_token_id in out_pa['input_ids'][0]      )
							self.assertFalse(0 in out_pa['attention_mask'][0]      )
							# short slice pair does have padding
							self.assertTrue(pad_token_id in out_pa['input_ids'][1]      )
							self.assertTrue(0 in out_pa['attention_mask'][1]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   List[str]:
							A						   =   '$$$'
							A						   =   GPTaTokenizer.from_pretrained(self.tmpdirname  ,bos_token=A_  ,add_bos_token=A_      )

							A						   =   'This is a simple input'
							A						   =   ['This is a simple input 1', 'This is a simple input 2']

							A						   =   tokenizer.bos_token_id

							A						   =   tokenizer(A_      )
							A						   =   tokenizer(A_      )

							self.assertEqual(out_s.input_ids[0]  ,A_      )
							self.assertTrue(all(o[0] == bos_token_id for o in out_sa.input_ids      )      )

							A						   =   tokenizer.decode(out_s.input_ids      )
							A						   =   tokenizer.batch_decode(out_sa.input_ids      )

							self.assertEqual(decode_s.split()[0]  ,A_      )
							self.assertTrue(all(d.split()[0] == bos_token for d in decode_sa      )      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   Dict:
							pass




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Any:
							# TODO: change to self.get_tokenizers() when the fast version is implemented
							A						   =   [self.get_tokenizer(do_lower_case=A_  ,add_bos_token=A_      )]
							for tokenizer in tokenizers:
								with self.subTest(F'{tokenizer.__class__.__name__}'      ):
									A						   =   'Encode this.'
									A						   =   'This one too please.'
									A						   =   tokenizer.encode(A_  ,add_special_tokens=A_      )
									encoded_sequence += tokenizer.encode(A_  ,add_special_tokens=A_      )
									A						   =   tokenizer.encode_plus(
									    A_  ,A_  ,add_special_tokens=A_  ,return_special_tokens_mask=A_  ,)
									A						   =   encoded_sequence_dict['input_ids']
									A						   =   encoded_sequence_dict['special_tokens_mask']
									self.assertEqual(len(A_      )  ,len(A_      )      )

									A						   =   [
									    (x if not special_tokens_mask[i] else None) for i, x in enumerate(A_      )
									]
									A						   =   [x for x in filtered_sequence if x is not None]
									self.assertEqual(A_  ,A_      )







@require_tokenizers
class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   List[str]:
							# More context:
							# https://huggingface.co/wjmcat/opt-350m-paddle/discussions/1
							# https://huggingface.slack.com/archives/C01N44FJDHT/p1653511495183519
							# https://github.com/huggingface/transformers/pull/17088#discussion_r871246439

							A						   =   AutoTokenizer.from_pretrained('facebook/opt-350m'  ,from_slow=A_      )
							A						   =   'A photo of a cat'

							A						   =   tokenizer.encode(
							    A_  ,)
							self.assertEqual(A_  ,[2, 250, 1345, 9, 10, 4758]      )
							tokenizer.save_pretrained('test_opt'      )

							A						   =   AutoTokenizer.from_pretrained('./test_opt'      )
							A						   =   tokenizer.encode(
							    A_  ,)
							self.assertEqual(A_  ,[2, 250, 1345, 9, 10, 4758]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   Optional[int]:
							A						   =   AutoTokenizer.from_pretrained('facebook/opt-350m'  ,use_slow=A_      )
							A						   =   'A photo of a cat'

							A						   =   tokenizer.encode(
							    A_  ,)
							# Same as above
							self.assertEqual(A_  ,[2, 250, 1345, 9, 10, 4758]      )




						@unittest.skip('This test is failing because of a bug in the fast tokenizer'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Optional[Any]:
							A						   =   AutoTokenizer.from_pretrained('facebook/opt-350m'  ,from_slow=A_      )

							A						   =   'bos'
							A						   =   tokenizer.get_vocab()['bos']

							A						   =   'A photo of a cat'
							A						   =   tokenizer.encode(
							    A_  ,)
							# We changed the bos token
							self.assertEqual(A_  ,[3_1957, 250, 1345, 9, 10, 4758]      )
							tokenizer.save_pretrained('./tok'      )
							A						   =   AutoTokenizer.from_pretrained('./tok'      )
							self.assertTrue(tokenizer.is_fast      )
							A						   =   tokenizer.encode(
							    A_  ,)
							self.assertEqual(A_  ,[3_1957, 250, 1345, 9, 10, 4758]      )

"""simple docstring"""


import sys
from collections import defaultdict







class 				lowerCAmelCase_				:



						'''simple docstring'''


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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      int      )     ->   Optional[int]:
							return self.node_position[vertex]


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      List[Any]  ,A_     :      Any      )     ->   List[Any]:
							A						   =   pos


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      str  ,A_     :      str  ,A_     :      Dict  ,A_     :      List[str]      )     ->   str:
							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 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      Optional[int]  ,A_     :      Dict  ,A_     :      str  ,A_     :      Union[str, Any]      )     ->   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 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Tuple  ,A_     :      Dict      )     ->   Union[str, Any]:
							A						   =   len(A_      ) // 2 - 1
							for i in range(A_  ,-1  ,-1      ):
								self.top_to_bottom(A_  ,A_  ,len(A_      )  ,A_      )




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[int]  ,A_     :      Dict      )     ->   Union[str, Any]:
							A						   =   positions[0]
							A						   =   sys.maxsize
							self.top_to_bottom(A_  ,0  ,len(A_      )  ,A_      )
							return temp






def       _snake_case				(		snake_case__   :     Dict     ):
	A						   =   Heap()

	A						   =   [0] * len(snake_case__     )
	A						   =   [-1] * len(snake_case__     )  # 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(snake_case__     )     ):
		distance_tv.append(sys.maxsize     )
		positions.append(snake_case__     )
		heap.node_position.append(snake_case__     )

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

	for _ in range(1	,      len(snake_case__     )     ):
		A						   =   heap.delete_minimum(snake_case__	,      snake_case__     )
		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(snake_case__     )]
				):
					A						   =   distance
					heap.bottom_to_top(
					    snake_case__	,      heap.get_position(snake_case__     )	,      snake_case__	,      snake_case__     )
					A						   =   vertex
	return tree_edges


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