




import sys
from collections import defaultdict
class       a__   :






						def __init__(       self      ):




											"""simple docstring"""



											__lowerCAmelCase           =	[]






						def     __SCREAMING_SNAKE_CASE(       self		,      _A      ):




											"""simple docstring"""



											return self.node_position[vertex]






						def     __SCREAMING_SNAKE_CASE(       self		,      _A		,      _A      ):




											"""simple docstring"""



											__lowerCAmelCase           =	pos






						def     __SCREAMING_SNAKE_CASE(       self		,      _A		,      _A		,      _A		,      _A      ):




											"""simple docstring"""



											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     __SCREAMING_SNAKE_CASE(       self		,      _A		,      _A		,      _A		,      _A      ):




											"""simple docstring"""



											__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     __SCREAMING_SNAKE_CASE(       self		,      _A		,      _A      ):




											"""simple docstring"""



											__lowerCAmelCase           =	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		,      _A		,      _A      ):




											"""simple docstring"""



											__lowerCAmelCase           =	positions[0]
											__lowerCAmelCase           =	sys.maxsize
											self.top_to_bottom(_A		,      0		,      len(_A      )		,      _A      )
											return temp







def      _a				(						SCREAMING_SNAKE_CASE_							:    Union[str, Any]					):
					__lowerCAmelCase           =	Heap()

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

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

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


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










from __future__ import annotations

import copy
import tempfile
import unittest

from transformers import CONFIG_MAPPING, AutoConfig, BertConfig, GPTaConfig, TaConfig, TapasConfig, is_tf_available
from transformers.testing_utils import (
    DUMMY_UNKNOWN_IDENTIFIER,
    SMALL_MODEL_IDENTIFIER,
    RequestCounter,
    require_tensorflow_probability,
    require_tf,
    slow,
)

from ..bert.test_modeling_bert import BertModelTester


if is_tf_available():
					from transformers import (
					    TFAutoModel,
					    TFAutoModelForCausalLM,
					    TFAutoModelForMaskedLM,
					    TFAutoModelForPreTraining,
					    TFAutoModelForQuestionAnswering,
					    TFAutoModelForSeqaSeqLM,
					    TFAutoModelForSequenceClassification,
					    TFAutoModelForTableQuestionAnswering,
					    TFAutoModelForTokenClassification,
					    TFAutoModelWithLMHead,
					    TFBertForMaskedLM,
					    TFBertForPreTraining,
					    TFBertForQuestionAnswering,
					    TFBertForSequenceClassification,
					    TFBertModel,
					    TFFunnelBaseModel,
					    TFFunnelModel,
					    TFGPTaLMHeadModel,
					    TFRobertaForMaskedLM,
					    TFTaForConditionalGeneration,
					    TFTapasForQuestionAnswering,
					)
					from transformers.models.auto.modeling_tf_auto import (
					    TF_MODEL_FOR_CAUSAL_LM_MAPPING,
					    TF_MODEL_FOR_MASKED_LM_MAPPING,
					    TF_MODEL_FOR_PRETRAINING_MAPPING,
					    TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
					    TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
					    TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
					    TF_MODEL_MAPPING,
					)
					from transformers.models.bert.modeling_tf_bert import TF_BERT_PRETRAINED_MODEL_ARCHIVE_LIST
					from transformers.models.gpta.modeling_tf_gpta import TF_GPT2_PRETRAINED_MODEL_ARCHIVE_LIST
					from transformers.models.ta.modeling_tf_ta import TF_T5_PRETRAINED_MODEL_ARCHIVE_LIST
					from transformers.models.tapas.modeling_tf_tapas import TF_TAPAS_PRETRAINED_MODEL_ARCHIVE_LIST
class       a__   ( snake_case__				):
						_a							:   Optional[int] =   """new-model"""


if is_tf_available():
					class       a__   ( snake_case__				):
											_a							:   Dict =   NewModelConfig
@require_tf
class       a__   ( unittest.TestCase				):






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											__lowerCAmelCase           =	"bert-base-cased"
											__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
											self.assertIsNotNone(_A      )
											self.assertIsInstance(_A		,      _A      )

											__lowerCAmelCase           =	TFAutoModel.from_pretrained(_A      )
											self.assertIsNotNone(_A      )
											self.assertIsInstance(_A		,      _A      )






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											__lowerCAmelCase           =	"bert-base-cased"
											__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
											self.assertIsNotNone(_A      )
											self.assertIsInstance(_A		,      _A      )

											__lowerCAmelCase           =	TFAutoModelForPreTraining.from_pretrained(_A      )
											self.assertIsNotNone(_A      )
											self.assertIsInstance(_A		,      _A      )






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											for model_name in TF_GPT2_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )

																__lowerCAmelCase           =	TFAutoModelForCausalLM.from_pretrained(_A      )
																__lowerCAmelCase       ,							__lowerCAmelCase           =	TFAutoModelForCausalLM.from_pretrained(_A		,      output_loading_info=_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											for model_name in TF_BERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )

																__lowerCAmelCase           =	TFAutoModelWithLMHead.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											for model_name in TF_BERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )

																__lowerCAmelCase           =	TFAutoModelForMaskedLM.from_pretrained(_A      )
																__lowerCAmelCase       ,							__lowerCAmelCase           =	TFAutoModelForMaskedLM.from_pretrained(_A		,      output_loading_info=_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											for model_name in TF_T5_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )

																__lowerCAmelCase           =	TFAutoModelForSeqaSeqLM.from_pretrained(_A      )
																__lowerCAmelCase       ,							__lowerCAmelCase           =	TFAutoModelForSeqaSeqLM.from_pretrained(_A		,      output_loading_info=_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											for model_name in ["bert-base-uncased"]:
																__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )

																__lowerCAmelCase           =	TFAutoModelForSequenceClassification.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )






						@slow
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											for model_name in ["bert-base-uncased"]:
																__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )

																__lowerCAmelCase           =	TFAutoModelForQuestionAnswering.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )






						@slow
						@require_tensorflow_probability
						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											for model_name in TF_TAPAS_PRETRAINED_MODEL_ARCHIVE_LIST[5:6]:
																__lowerCAmelCase           =	AutoConfig.from_pretrained(_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )

																__lowerCAmelCase           =	TFAutoModelForTableQuestionAnswering.from_pretrained(_A      )
																__lowerCAmelCase       ,							__lowerCAmelCase           =	TFAutoModelForTableQuestionAnswering.from_pretrained(
																    _A		,      output_loading_info=_A      )
																self.assertIsNotNone(_A      )
																self.assertIsInstance(_A		,      _A      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											__lowerCAmelCase           =	TFAutoModelWithLMHead.from_pretrained(_A      )
											self.assertIsInstance(_A		,      _A      )
											self.assertEqual(model.num_parameters()		,      1_4_4_1_0      )
											self.assertEqual(model.num_parameters(only_trainable=_A      )		,      1_4_4_1_0      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											__lowerCAmelCase           =	TFAutoModelWithLMHead.from_pretrained(_A      )
											self.assertIsInstance(_A		,      _A      )
											self.assertEqual(model.num_parameters()		,      1_4_4_1_0      )
											self.assertEqual(model.num_parameters(only_trainable=_A      )		,      1_4_4_1_0      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											__lowerCAmelCase           =	TFAutoModel.from_pretrained("sgugger/funnel-random-tiny"      )
											self.assertIsInstance(_A		,      _A      )

											__lowerCAmelCase           =	copy.deepcopy(model.config      )
											__lowerCAmelCase           =	["FunnelBaseModel"]
											__lowerCAmelCase           =	TFAutoModel.from_config(_A      )
											self.assertIsInstance(_A		,      _A      )

											with tempfile.TemporaryDirectory() as tmp_dir:
																model.save_pretrained(_A      )
																__lowerCAmelCase           =	TFAutoModel.from_pretrained(_A      )
																self.assertIsInstance(_A		,      _A      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											try:
																AutoConfig.register("new-model"		,      _A      )

																__lowerCAmelCase           =	[
																    TFAutoModel,
																    TFAutoModelForCausalLM,
																    TFAutoModelForMaskedLM,
																    TFAutoModelForPreTraining,
																    TFAutoModelForQuestionAnswering,
																    TFAutoModelForSequenceClassification,
																    TFAutoModelForTokenClassification,
																]

																for auto_class in auto_classes:
																					with self.subTest(auto_class.__name__      ):
																										# Wrong config class will raise an error
																										with self.assertRaises(_A      ):
																															auto_class.register(_A		,      _A      )
																										auto_class.register(_A		,      _A      )
																										# Trying to register something existing in the Transformers library will raise an error
																										with self.assertRaises(_A      ):
																															auto_class.register(_A		,      _A      )

																										# Now that the config is registered, it can be used as any other config with the auto-API
																										__lowerCAmelCase           =	BertModelTester(self      ).get_config()
																										__lowerCAmelCase           =	NewModelConfig(**tiny_config.to_dict()      )
																										__lowerCAmelCase           =	auto_class.from_config(_A      )
																										self.assertIsInstance(_A		,      _A      )

																										with tempfile.TemporaryDirectory() as tmp_dir:
																															model.save_pretrained(_A      )
																															__lowerCAmelCase           =	auto_class.from_pretrained(_A      )
																															self.assertIsInstance(_A		,      _A      )

											finally:
																if "new-model" in CONFIG_MAPPING._extra_content:
																					del CONFIG_MAPPING._extra_content["new-model"]
																for mapping in (
																    TF_MODEL_MAPPING,
																    TF_MODEL_FOR_PRETRAINING_MAPPING,
																    TF_MODEL_FOR_QUESTION_ANSWERING_MAPPING,
																    TF_MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
																    TF_MODEL_FOR_TOKEN_CLASSIFICATION_MAPPING,
																    TF_MODEL_FOR_CAUSAL_LM_MAPPING,
																    TF_MODEL_FOR_MASKED_LM_MAPPING,
																):
																					if NewModelConfig in mapping._extra_content:
																										del mapping._extra_content[NewModelConfig]






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											with self.assertRaisesRegex(
											    _A		,      "bert-base is not a local folder and is not a valid model identifier"      ):
																__lowerCAmelCase           =	TFAutoModel.from_pretrained("bert-base"      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											with self.assertRaisesRegex(
											    _A		,      R"aaaaaa is not a valid git identifier \(branch name, tag name or commit id\)"      ):
																__lowerCAmelCase           =	TFAutoModel.from_pretrained(_A		,      revision="aaaaaa"      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											with self.assertRaisesRegex(
											    _A		,      "hf-internal-testing/config-no-model does not appear to have a file named pytorch_model.bin"		,      ):
																__lowerCAmelCase           =	TFAutoModel.from_pretrained("hf-internal-testing/config-no-model"      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											with self.assertRaisesRegex(_A		,      "Use `from_pt=True` to load this model"      ):
																__lowerCAmelCase           =	TFAutoModel.from_pretrained("hf-internal-testing/tiny-bert-pt-only"      )






						def     __SCREAMING_SNAKE_CASE(       self      ):




											"""simple docstring"""



											__lowerCAmelCase           =	TFAutoModel.from_pretrained("hf-internal-testing/tiny-random-bert"      )
											with RequestCounter() as counter:
																__lowerCAmelCase           =	TFAutoModel.from_pretrained("hf-internal-testing/tiny-random-bert"      )
																self.assertEqual(counter.get_request_count		,      0      )
																self.assertEqual(counter.head_request_count		,      1      )
																self.assertEqual(counter.other_request_count		,      0      )

											# With a sharded checkpoint
											__lowerCAmelCase           =	TFAutoModel.from_pretrained("ArthurZ/tiny-random-bert-sharded"      )
											with RequestCounter() as counter:
																__lowerCAmelCase           =	TFAutoModel.from_pretrained("ArthurZ/tiny-random-bert-sharded"      )
																self.assertEqual(counter.get_request_count		,      0      )
																self.assertEqual(counter.head_request_count		,      1      )
																self.assertEqual(counter.other_request_count		,      0      )




