


"""simple docstring"""


import inspect
import unittest

import numpy as np

from transformers import ViTConfig, is_flax_available
from transformers.testing_utils import require_flax, slow

from ...test_configuration_common import ConfigTester
from ...test_modeling_flax_common import FlaxModelTesterMixin, floats_tensor


if is_flax_available():
	import jax

	from transformers.models.vit.modeling_flax_vit import FlaxViTForImageClassification, FlaxViTModel
class   _UpperCamelCase  (   unittest.TestCase		):
							'''simple docstring'''







							def __init__(     self    ,   __a    ,   __a=13    ,   __a=30    ,   __a=2    ,   __a=3    ,   __a=True    ,   __a=True    ,   __a=32    ,   __a=5    ,   __a=4    ,   __a=37    ,   __a="gelu"    ,   __a=0.1    ,   __a=0.1    ,   __a=10    ,   __a=0.0_2    ,   ):
										__lowerCAmelCase				    =			parent
										__lowerCAmelCase				    =			batch_size
										__lowerCAmelCase				    =			image_size
										__lowerCAmelCase				    =			patch_size
										__lowerCAmelCase				    =			num_channels
										__lowerCAmelCase				    =			is_training
										__lowerCAmelCase				    =			use_labels
										__lowerCAmelCase				    =			hidden_size
										__lowerCAmelCase				    =			num_hidden_layers
										__lowerCAmelCase				    =			num_attention_heads
										__lowerCAmelCase				    =			intermediate_size
										__lowerCAmelCase				    =			hidden_act
										__lowerCAmelCase				    =			hidden_dropout_prob
										__lowerCAmelCase				    =			attention_probs_dropout_prob
										__lowerCAmelCase				    =			type_sequence_label_size
										__lowerCAmelCase				    =			initializer_range

										# in ViT, the seq length equals the number of patches + 1 (we add 1 for the [CLS] token)
										__lowerCAmelCase				    =			(image_size // patch_size) ** 2
										__lowerCAmelCase				    =			num_patches + 1

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]	)

										__lowerCAmelCase				    =			ViTConfig(
										    image_size=self.image_size    ,   patch_size=self.patch_size    ,   num_channels=self.num_channels    ,   hidden_size=self.hidden_size    ,   num_hidden_layers=self.num_hidden_layers    ,   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    ,   is_decoder=__a    ,   initializer_range=self.initializer_range    ,   )

										return config, pixel_values

							def 			snake_case				(     self    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			FlaxViTModel(config=__a	)
										__lowerCAmelCase				    =			model(__a	)
										# expected sequence length = num_patches + 1 (we add 1 for the [CLS] token)
										__lowerCAmelCase				    =			(self.image_size, self.image_size)
										__lowerCAmelCase				    =			(self.patch_size, self.patch_size)
										__lowerCAmelCase				    =			(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])
										self.parent.assertEqual(result.last_hidden_state.shape    ,   (self.batch_size, num_patches + 1, self.hidden_size)	)

							def 			snake_case				(     self    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			self.type_sequence_label_size
										__lowerCAmelCase				    =			FlaxViTForImageClassification(config=__a	)
										__lowerCAmelCase				    =			model(__a	)
										self.parent.assertEqual(result.logits.shape    ,   (self.batch_size, self.type_sequence_label_size)	)

										# test greyscale images
										__lowerCAmelCase				    =			1
										__lowerCAmelCase				    =			FlaxViTForImageClassification(__a	)

										__lowerCAmelCase				    =			floats_tensor([self.batch_size, 1, self.image_size, self.image_size]	)
										__lowerCAmelCase				    =			model(__a	)



							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.prepare_config_and_inputs()
										(
										    (
										    __lowerCAmelCase
										)    ,	(
										    __lowerCAmelCase
										)    ,	
										)				    =			config_and_inputs
										__lowerCAmelCase				    =			{"pixel_values": pixel_values}
										return config, inputs_dict
@require_flax
class   _UpperCamelCase  (   lowerCAmelCase__       ,unittest.TestCase		):
							'''simple docstring'''







							__UpperCAmelCase						:    int				      =(FlaxViTModel, FlaxViTForImageClassification) if is_flax_available() else ()

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			FlaxViTModelTester(self	)
										__lowerCAmelCase				    =			ConfigTester(self    ,   config_class=__a    ,   has_text_modality=__a    ,   hidden_size=37	)

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

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_model(*__a	)

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_image_classification(*__a	)

							def 			snake_case				(     self	):
										__lowerCAmelCase    ,	__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs_for_common()

										for model_class in self.all_model_classes:
													__lowerCAmelCase				    =			model_class(__a	)
													__lowerCAmelCase				    =			inspect.signature(model.__call__	)
													# signature.parameters is an OrderedDict => so arg_names order is deterministic
													__lowerCAmelCase				    =			[*signature.parameters.keys()]

													__lowerCAmelCase				    =			["pixel_values"]
													self.assertListEqual(arg_names[:1]    ,   __a	)

							def 			snake_case				(     self	):
										__lowerCAmelCase    ,	__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs_for_common()

										for model_class in self.all_model_classes:
													with self.subTest(model_class.__name__	):
																__lowerCAmelCase				    =			self._prepare_for_class(__a    ,   __a	)
																__lowerCAmelCase				    =			model_class(__a	)

																@jax.jit
																def model_jitted(__a    ,   **__a	):
																			return model(pixel_values=__a    ,   **__a	)

																with self.subTest("JIT Enabled"	):
																			__lowerCAmelCase				    =			model_jitted(**__a	).to_tuple()

																with self.subTest("JIT Disabled"	):
																			with jax.disable_jit():
																						__lowerCAmelCase				    =			model_jitted(**__a	).to_tuple()

																self.assertEqual(len(__a	)    ,   len(__a	)	)
																for jitted_output, output in zip(__a    ,   __a	):
																			self.assertEqual(jitted_output.shape    ,   output.shape	)



							@slow
							def 			snake_case				(     self	):
										for model_class_name in self.all_model_classes:
													__lowerCAmelCase				    =			model_class_name.from_pretrained("google/vit-base-patch16-224"	)
													__lowerCAmelCase				    =			model(np.ones((1, 3, 2_24, 2_24)	)	)
													self.assertIsNotNone(__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))




