


from __future__ import annotations

import unittest

from transformers import EsmConfig, is_tf_available
from transformers.testing_utils import require_tf, slow

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


if is_tf_available():
				import numpy
				import tensorflow as tf

				from transformers.models.esm.modeling_tf_esm import (
				    TF_ESM_PRETRAINED_MODEL_ARCHIVE_LIST,
				    TFEsmForMaskedLM,
				    TFEsmForSequenceClassification,
				    TFEsmForTokenClassification,
				    TFEsmModel,
				)






class       _UpperCamelCase    :

				"""simple docstring"""







				def __init__(						self				,   a__				,   )	->				Optional[Any]:
					A								=				parent
					A								=				13
					A								=				7
					A								=				True
					A								=				True
					A								=				True
					A								=				99
					A								=				32
					A								=				2
					A								=				4
					A								=				37
					A								=				"""gelu"""
					A								=				0.1
					A								=				0.1
					A								=				512
					A								=				16
					A								=				2
					A								=				0.02
					A								=				3
					A								=				4
					A								=				None

				def      _UpperCAmelCase					(						self   )	->				Dict:
					A								=				ids_tensor([self.batch_size, self.seq_length]				,   self.vocab_size   )

					A								=				None
					if self.use_input_mask:
						A								=				random_attention_mask([self.batch_size, self.seq_length]   )

					A								=				None
					A								=				None
					A								=				None
					if self.use_labels:
						A								=				ids_tensor([self.batch_size]				,   self.type_sequence_label_size   )
						A								=				ids_tensor([self.batch_size, self.seq_length]				,   self.num_labels   )
						A								=				ids_tensor([self.batch_size]				,   self.num_choices   )

					A								=				EsmConfig(
					    vocab_size=self.vocab_size				,   hidden_size=self.hidden_size				,   num_hidden_layers=self.num_hidden_layers				,   pad_token_id=1				,   num_attention_heads=self.num_attention_heads				,   intermediate_size=self.intermediate_size				,   hidden_act=self.hidden_act				,   hidden_dropout_prob=self.hidden_dropout_prob				,   attention_probs_dropout_prob=self.attention_probs_dropout_prob				,   max_position_embeddings=self.max_position_embeddings				,   type_vocab_size=self.type_vocab_size				,   initializer_range=self.initializer_range				,   )

					return config, input_ids, input_mask, sequence_labels, token_labels, choice_labels

				def      _UpperCAmelCase					(						self   )	->				Union[str, Any]:
					(
					    (
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			
					)								=				self.prepare_config_and_inputs()

					A								=				True
					A								=				floats_tensor([self.batch_size, self.seq_length, self.hidden_size]   )
					A								=				ids_tensor([self.batch_size, self.seq_length]				,   vocab_size=2   )

					return (
					    config,
					    input_ids,
					    input_mask,
					    sequence_labels,
					    token_labels,
					    choice_labels,
					    encoder_hidden_states,
					    encoder_attention_mask,
					)

				def      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__				,   a__				,   a__   )	->				Optional[int]:
					A								=				TFEsmModel(config=a__   )
					A								=				{"""input_ids""": input_ids, """attention_mask""": input_mask}
					A								=				model(a__   )

					A								=				[input_ids, input_mask]
					A								=				model(a__   )

					A								=				model(a__   )

					self.parent.assertEqual(result.last_hidden_state.shape				,   (self.batch_size, self.seq_length, self.hidden_size)   )

				def      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__				,   a__				,   a__				,   a__				,   a__				,   )	->				List[Any]:
					A								=				True

					A								=				TFEsmModel(config=a__   )
					A								=				{
					    """input_ids""": input_ids,
					    """attention_mask""": input_mask,
					    """encoder_hidden_states""": encoder_hidden_states,
					    """encoder_attention_mask""": encoder_attention_mask,
					}
					A								=				model(a__   )

					A								=				[input_ids, input_mask]
					A								=				model(a__				,   encoder_hidden_states=a__   )

					# Also check the case where encoder outputs are not passed
					A								=				model(a__				,   attention_mask=a__   )

					self.parent.assertEqual(result.last_hidden_state.shape				,   (self.batch_size, self.seq_length, self.hidden_size)   )

				def      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__				,   a__				,   a__   )	->				Optional[Any]:
					A								=				TFEsmForMaskedLM(config=a__   )
					A								=				model([input_ids, input_mask]   )
					self.parent.assertEqual(result.logits.shape				,   (self.batch_size, self.seq_length, self.vocab_size)   )

				def      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__				,   a__				,   a__   )	->				Dict:
					A								=				self.num_labels
					A								=				TFEsmForTokenClassification(config=a__   )
					A								=				{"""input_ids""": input_ids, """attention_mask""": input_mask}
					A								=				model(a__   )
					self.parent.assertEqual(result.logits.shape				,   (self.batch_size, self.seq_length, self.num_labels)   )

				def      _UpperCAmelCase					(						self   )	->				Union[str, Any]:
					A								=				self.prepare_config_and_inputs()
					(
					    (
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			(
					    A
					)					,			
					)								=				config_and_inputs
					A								=				{"""input_ids""": input_ids, """attention_mask""": input_mask}
					return config, inputs_dict






@require_tf
class       _UpperCamelCase    (					__snake_case    ,		__snake_case    ,		unittest.TestCase				):

				"""simple docstring"""







				lowerCAmelCase 		= (
				    (
				        TFEsmModel,
				        TFEsmForMaskedLM,
				        TFEsmForSequenceClassification,
				        TFEsmForTokenClassification,
				    )
				    if is_tf_available()
				    else ()
				)
				lowerCAmelCase 		= (
				    {
				        'feature-extraction': TFEsmModel,
				        'fill-mask': TFEsmForMaskedLM,
				        'text-classification': TFEsmForSequenceClassification,
				        'token-classification': TFEsmForTokenClassification,
				        'zero-shot': TFEsmForSequenceClassification,
				    }
				    if is_tf_available()
				    else {}
				)
				lowerCAmelCase 		= False
				lowerCAmelCase 		= False

				def      _UpperCAmelCase					(						self   )	->				Union[str, Any]:
					A								=				TFEsmModelTester(self   )
					A								=				ConfigTester(self				,   config_class=a__				,   hidden_size=37   )

				def      _UpperCAmelCase					(						self   )	->				Optional[int]:
					self.config_tester.run_common_tests()

				def      _UpperCAmelCase					(						self   )	->				str:
					A								=				self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_model(*a__   )

				def      _UpperCAmelCase					(						self   )	->				List[Any]:
					A								=				self.model_tester.prepare_config_and_inputs_for_decoder()
					self.model_tester.create_and_check_model_as_decoder(*a__   )

				def      _UpperCAmelCase					(						self   )	->				Union[str, Any]:
					A								=				self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_masked_lm(*a__   )

				def      _UpperCAmelCase					(						self   )	->				Dict:
					A								=				self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_token_classification(*a__   )

				@slow
				def      _UpperCAmelCase					(						self   )	->				List[str]:
					for model_name in TF_ESM_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
						A								=				TFEsmModel.from_pretrained(a__   )
						self.assertIsNotNone(a__   )

				@unittest.skip("""Protein models do not support embedding resizing."""   )
				def      _UpperCAmelCase					(						self   )	->				Any:
					pass

				@unittest.skip("""Protein models do not support embedding resizing."""   )
				def      _UpperCAmelCase					(						self   )	->				int:
					pass

				def      _UpperCAmelCase					(						self   )	->				Optional[int]:
					A					,			A								=				self.model_tester.prepare_config_and_inputs_for_common()

					for model_class in self.all_model_classes:
						A								=				model_class(a__   )
						assert isinstance(model.get_input_embeddings()				,   tf.keras.layers.Layer   )
						if model_class is TFEsmForMaskedLM:
							# Output embedding test differs from the main test because they're a matrix, not a layer
							A								=				model.get_bias()
							assert isinstance(a__				,   a__   )
							for k, v in name.items():
								assert isinstance(a__				,   tf.Variable   )
						else:
							A								=				model.get_output_embeddings()
							assert x is None
							A								=				model.get_bias()
							assert name is None






@require_tf
class       _UpperCamelCase    (					unittest.TestCase				):

				"""simple docstring"""







				@slow
				def      _UpperCAmelCase					(						self   )	->				Dict:
					A								=				TFEsmForMaskedLM.from_pretrained("""facebook/esm2_t6_8M_UR50D"""   )

					A								=				tf.constant([[0, 1, 2, 3, 4, 5]]   )
					A								=				model(a__   )[0]
					A								=				[1, 6, 33]
					self.assertEqual(list(output.numpy().shape   )				,   a__   )
					# compare the actual values for a slice.
					A								=				tf.constant(
					    [
					        [
					            [8.92_15_18, -10.58_98_14, -6.4_67_13_07],
					            [-6.3_96_71_56, -13.91_13_77, -1.1_21_19_15],
					            [-7.78_12_47, -13.95_15_57, -3.74_05_92],
					        ]
					    ]   )
					self.assertTrue(numpy.allclose(output[:, :3, :3].numpy()				,   expected_slice.numpy()				,   atol=1e-2   )   )

				@slow
				def      _UpperCAmelCase					(						self   )	->				Optional[int]:
					A								=				TFEsmModel.from_pretrained("""facebook/esm2_t6_8M_UR50D"""   )

					A								=				tf.constant([[0, 6, 4, 13, 5, 4, 16, 12, 11, 7, 2]]   )
					A								=				model(a__   )[0]
					# compare the actual values for a slice.
					A								=				tf.constant(
					    [
					        [
					            [0.14_44_30_92, 0.54_12_53_27, 0.3_24_77_39],
					            [0.30_34_04_84, 0.00_52_66_76, 0.31_07_77_22],
					            [0.32_27_80_43, -0.24_98_70_96, 0.3_41_46_28],
					        ]
					    ]   )
					self.assertTrue(numpy.allclose(output[:, :3, :3].numpy()				,   expected_slice.numpy()				,   atol=1e-4   )   )







import sys
from collections import defaultdict






class       _UpperCamelCase    :

				"""simple docstring"""







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

				def      _UpperCAmelCase					(						self				,   a__   )	->				List[str]:
					return self.node_position[vertex]

				def      _UpperCAmelCase					(						self				,   a__				,   a__   )	->				Optional[int]:
					A								=				pos

				def      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__   )	->				Any:
					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      _UpperCAmelCase					(						self				,   a__				,   a__				,   a__				,   a__   )	->				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      _UpperCAmelCase					(						self				,   a__				,   a__   )	->				Optional[int]:
					A								=				len(a__   ) // 2 - 1
					for i in range(a__				,   -1				,   -1   ):
						self.top_to_bottom(a__				,   a__				,   len(a__   )				,   a__   )

				def      _UpperCAmelCase					(						self				,   a__				,   a__   )	->				Any:
					A								=				positions[0]
					A								=				sys.maxsize
					self.top_to_bottom(a__				,   0				,   len(a__   )				,   a__   )
					return temp





def   _lowerCAmelCase				(   UpperCamelCase__:     List[str]						) ->   List[str]:





	"""simple docstring"""







	A								=				Heap()

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

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

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


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



