


"""simple docstring"""


from __future__ import annotations

import unittest

from transformers import BlenderbotSmallConfig, BlenderbotSmallTokenizer, is_tf_available
from transformers.testing_utils import require_tf, require_tokenizers, slow
from transformers.utils import cached_property

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
	import tensorflow as tf

	from transformers import TFAutoModelForSeqaSeqLM, TFBlenderbotSmallForConditionalGeneration, TFBlenderbotSmallModel
@require_tf
class   _UpperCamelCase  :
							'''simple docstring'''







							__UpperCAmelCase						:    Optional[Any]				      =BlenderbotSmallConfig
							__UpperCAmelCase						:    Tuple				      ={}
							__UpperCAmelCase						:    Dict				      ="""gelu"""

							def __init__(     self    ,   __a    ,   __a=13    ,   __a=7    ,   __a=True    ,   __a=False    ,   __a=99    ,   __a=32    ,   __a=2    ,   __a=4    ,   __a=37    ,   __a=0.1    ,   __a=0.1    ,   __a=20    ,   __a=2    ,   __a=1    ,   __a=0    ,   ):
										__lowerCAmelCase				    =			parent
										__lowerCAmelCase				    =			batch_size
										__lowerCAmelCase				    =			seq_length
										__lowerCAmelCase				    =			is_training
										__lowerCAmelCase				    =			use_labels
										__lowerCAmelCase				    =			vocab_size
										__lowerCAmelCase				    =			hidden_size
										__lowerCAmelCase				    =			num_hidden_layers
										__lowerCAmelCase				    =			num_attention_heads
										__lowerCAmelCase				    =			intermediate_size

										__lowerCAmelCase				    =			hidden_dropout_prob
										__lowerCAmelCase				    =			attention_probs_dropout_prob
										__lowerCAmelCase				    =			max_position_embeddings
										__lowerCAmelCase				    =			eos_token_id
										__lowerCAmelCase				    =			pad_token_id
										__lowerCAmelCase				    =			bos_token_id

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			ids_tensor([self.batch_size, self.seq_length - 1]    ,   self.vocab_size	)
										__lowerCAmelCase				    =			tf.expand_dims(tf.constant([self.eos_token_id] * self.batch_size	)    ,   1	)
										__lowerCAmelCase				    =			tf.concat([input_ids, eos_tensor]    ,   axis=1	)

										__lowerCAmelCase				    =			ids_tensor([self.batch_size, self.seq_length]    ,   self.vocab_size	)

										__lowerCAmelCase				    =			self.config_cls(
										    vocab_size=self.vocab_size    ,   d_model=self.hidden_size    ,   encoder_layers=self.num_hidden_layers    ,   decoder_layers=self.num_hidden_layers    ,   encoder_attention_heads=self.num_attention_heads    ,   decoder_attention_heads=self.num_attention_heads    ,   encoder_ffn_dim=self.intermediate_size    ,   decoder_ffn_dim=self.intermediate_size    ,   dropout=self.hidden_dropout_prob    ,   attention_dropout=self.attention_probs_dropout_prob    ,   max_position_embeddings=self.max_position_embeddings    ,   eos_token_ids=[2]    ,   bos_token_id=self.bos_token_id    ,   pad_token_id=self.pad_token_id    ,   decoder_start_token_id=self.pad_token_id    ,   **self.config_updates    ,   )
										__lowerCAmelCase				    =			prepare_blenderbot_small_inputs_dict(__a    ,   __a    ,   __a	)
										return config, inputs_dict



							def 			snake_case				(     self    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			TFBlenderbotSmallModel(config=__a	).get_decoder()
										__lowerCAmelCase				    =			inputs_dict["input_ids"]

										__lowerCAmelCase				    =			input_ids[:1, :]
										__lowerCAmelCase				    =			inputs_dict["attention_mask"][:1, :]
										__lowerCAmelCase				    =			inputs_dict["head_mask"]
										__lowerCAmelCase				    =			1

										# first forward pass
										__lowerCAmelCase				    =			model(__a    ,   attention_mask=__a    ,   head_mask=__a    ,   use_cache=__a	)

										__lowerCAmelCase    ,	__lowerCAmelCase				    =			outputs.to_tuple()

										# create hypothetical next token and extent to next_input_ids
										__lowerCAmelCase				    =			ids_tensor((self.batch_size, 3)    ,   config.vocab_size	)
										__lowerCAmelCase				    =			tf.cast(ids_tensor((self.batch_size, 3)    ,   2	)    ,   tf.inta	)

										# append to next input_ids and
										__lowerCAmelCase				    =			tf.concat([input_ids, next_tokens]    ,   axis=-1	)
										__lowerCAmelCase				    =			tf.concat([attention_mask, next_attn_mask]    ,   axis=-1	)

										__lowerCAmelCase				    =			model(__a    ,   attention_mask=__a	)[0]
										__lowerCAmelCase				    =			model(__a    ,   attention_mask=__a    ,   past_key_values=__a	)[0]

										self.parent.assertEqual(next_tokens.shape[1]    ,   output_from_past.shape[1]	)

										# select random slice
										__lowerCAmelCase				    =			int(ids_tensor((1,)    ,   output_from_past.shape[-1]	)	)
										__lowerCAmelCase				    =			output_from_no_past[:, -3:, random_slice_idx]
										__lowerCAmelCase				    =			output_from_past[:, :, random_slice_idx]

										# test that outputs are equal for slice
										tf.debugging.assert_near(__a    ,   __a    ,   rtol=1e-3	)


def _lowerCamelCase	(		_UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase    , _UpperCamelCase=None    , _UpperCamelCase=None    , _UpperCamelCase=None    , _UpperCamelCase=None    , _UpperCamelCase=None    , ):

			'''simple docstring'''




			if attention_mask is None:
						__lowerCAmelCase				    =			tf.cast(tf.math.not_equal(_UpperCamelCase    , config.pad_token_id      )    , tf.inta      )
			if decoder_attention_mask is None:
						__lowerCAmelCase				    =			tf.concat(
						    [
						        tf.ones(decoder_input_ids[:, :1].shape    , dtype=tf.inta      ),
						        tf.cast(tf.math.not_equal(decoder_input_ids[:, 1:]    , config.pad_token_id      )    , tf.inta      ),
						    ]    , axis=-1    , )
			if head_mask is None:
						__lowerCAmelCase				    =			tf.ones((config.encoder_layers, config.encoder_attention_heads)      )
			if decoder_head_mask is None:
						__lowerCAmelCase				    =			tf.ones((config.decoder_layers, config.decoder_attention_heads)      )
			if cross_attn_head_mask is None:
						__lowerCAmelCase				    =			tf.ones((config.decoder_layers, config.decoder_attention_heads)      )
			return {
			    "input_ids": input_ids,
			    "decoder_input_ids": decoder_input_ids,
			    "attention_mask": attention_mask,
			    "decoder_attention_mask": decoder_attention_mask,
			    "head_mask": head_mask,
			    "decoder_head_mask": decoder_head_mask,
			    "cross_attn_head_mask": cross_attn_head_mask,
			}
@require_tf
class   _UpperCamelCase  (   lowerCAmelCase__       ,lowerCAmelCase__       ,unittest.TestCase		):
							'''simple docstring'''







							__UpperCAmelCase						:    str				      =(
							    (TFBlenderbotSmallForConditionalGeneration, TFBlenderbotSmallModel) if is_tf_available() else ()
							)
							__UpperCAmelCase						:    Dict				      =(TFBlenderbotSmallForConditionalGeneration,) if is_tf_available() else ()
							__UpperCAmelCase						:    int				      =(
							    {
							        """conversational""": TFBlenderbotSmallForConditionalGeneration,
							        """feature-extraction""": TFBlenderbotSmallModel,
							        """summarization""": TFBlenderbotSmallForConditionalGeneration,
							        """text2text-generation""": TFBlenderbotSmallForConditionalGeneration,
							        """translation""": TFBlenderbotSmallForConditionalGeneration,
							    }
							    if is_tf_available()
							    else {}
							)
							__UpperCAmelCase						:    str				      =True
							__UpperCAmelCase						:    Tuple				      =False
							__UpperCAmelCase						:    Dict				      =False

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			TFBlenderbotSmallModelTester(self	)
										__lowerCAmelCase				    =			ConfigTester(self    ,   config_class=__a	)

							def 			snake_case				(     self	):
										self.config_tester.run_common_tests()



							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs_for_common()
										self.model_tester.check_decoder_model_past_large_inputs(*__a	)
@require_tokenizers
@require_tf
class   _UpperCamelCase  (   unittest.TestCase		):
							'''simple docstring'''







							__UpperCAmelCase						:    Optional[int]				      =[
							    """Social anxiety\nWow, I am never shy. Do you have anxiety?\nYes. I end up sweating and blushing and feel like """
							    """  i'm going to throw up.\nand why is that?"""
							]
							__UpperCAmelCase						:    Optional[int]				      ="""facebook/blenderbot_small-90M"""

							@cached_property
							def 			snake_case				(     self	):
										# use "old" tokenizer here because of bug when downloading new tokenizer
										return BlenderbotSmallTokenizer.from_pretrained("facebook/blenderbot-90M"	)

							@cached_property
							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			TFAutoModelForSeqaSeqLM.from_pretrained(self.model_name	)
										return model



							@slow
							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.tokenizer(self.src_text    ,   return_tensors="tf"	)
										__lowerCAmelCase				    =			self.model.generate(
										    model_inputs.input_ids    ,   attention_mask=model_inputs.attention_mask    ,   num_beams=2    ,   use_cache=__a    ,   )
										__lowerCAmelCase				    =			self.tokenizer.batch_decode(generated_ids.numpy()    ,   skip_special_tokens=__a	)[0]
										assert generated_words in (
										    "i don't know. i just feel like i'm going to throw up. it's not fun.",
										    "i'm not sure. i just feel like i've been feeling like i have to be in a certain place",
										    "i'm not sure. i just feel like i've been in a bad situation.",
										)








"""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))




