


"""simple docstring"""


import inspect
import unittest

from transformers import DPTConfig
from transformers.file_utils import is_torch_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
	import torch
	from torch import nn

	from transformers import MODEL_MAPPING, DPTForDepthEstimation, DPTForSemanticSegmentation, DPTModel
	from transformers.models.dpt.modeling_dpt import DPT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
	from PIL import Image

	from transformers import DPTImageProcessor
class   _UpperCamelCase  :
							'''simple docstring'''







							def __init__(     self    ,   __a    ,   __a=2    ,   __a=32    ,   __a=16    ,   __a=3    ,   __a=True    ,   __a=True    ,   __a=32    ,   __a=4    ,   __a=[0, 1, 2, 3]    ,   __a=4    ,   __a=37    ,   __a="gelu"    ,   __a=0.1    ,   __a=0.1    ,   __a=0.0_2    ,   __a=3    ,   __a=[1, 3_84, 24, 24]    ,   __a=True    ,   __a=None    ,   ):
										__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				    =			backbone_out_indices
										__lowerCAmelCase				    =			num_attention_heads
										__lowerCAmelCase				    =			intermediate_size
										__lowerCAmelCase				    =			hidden_act
										__lowerCAmelCase				    =			hidden_dropout_prob
										__lowerCAmelCase				    =			attention_probs_dropout_prob
										__lowerCAmelCase				    =			initializer_range
										__lowerCAmelCase				    =			num_labels
										__lowerCAmelCase				    =			backbone_featmap_shape
										__lowerCAmelCase				    =			scope
										__lowerCAmelCase				    =			is_hybrid
										# sequence length of DPT = num_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				    =			None
										if self.use_labels:
													__lowerCAmelCase				    =			ids_tensor([self.batch_size, self.image_size, self.image_size]    ,   self.num_labels	)

										__lowerCAmelCase				    =			self.get_config()

										return config, pixel_values, labels

							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			{
										    "global_padding": "same",
										    "layer_type": "bottleneck",
										    "depths": [3, 4, 9],
										    "out_features": ["stage1", "stage2", "stage3"],
										    "embedding_dynamic_padding": True,
										    "hidden_sizes": [96, 1_92, 3_84, 7_68],
										    "num_groups": 2,
										}

										return DPTConfig(
										    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    ,   backbone_out_indices=self.backbone_out_indices    ,   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    ,   is_hybrid=self.is_hybrid    ,   backbone_config=__a    ,   backbone_featmap_shape=self.backbone_featmap_shape    ,   )

							def 			snake_case				(     self    ,   __a    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			DPTModel(config=__a	)
										model.to(__a	)
										model.eval()
										__lowerCAmelCase				    =			model(__a	)
										self.parent.assertEqual(result.last_hidden_state.shape    ,   (self.batch_size, self.seq_length, self.hidden_size)	)

							def 			snake_case				(     self    ,   __a    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			self.num_labels
										__lowerCAmelCase				    =			DPTForDepthEstimation(__a	)
										model.to(__a	)
										model.eval()
										__lowerCAmelCase				    =			model(__a	)
										self.parent.assertEqual(result.predicted_depth.shape    ,   (self.batch_size, self.image_size, self.image_size)	)

							def 			snake_case				(     self    ,   __a    ,   __a    ,   __a	):
										__lowerCAmelCase				    =			self.num_labels
										__lowerCAmelCase				    =			DPTForSemanticSegmentation(__a	)
										model.to(__a	)
										model.eval()
										__lowerCAmelCase				    =			model(__a    ,   labels=__a	)
										self.parent.assertEqual(
										    result.logits.shape    ,   (self.batch_size, self.num_labels, self.image_size, self.image_size)	)



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







							__UpperCAmelCase						:    int				      =(DPTModel, DPTForDepthEstimation, DPTForSemanticSegmentation) if is_torch_available() else ()
							__UpperCAmelCase						:    List[Any]				      =(
							    {
							        """depth-estimation""": DPTForDepthEstimation,
							        """feature-extraction""": DPTModel,
							        """image-segmentation""": DPTForSemanticSegmentation,
							    }
							    if is_torch_available()
							    else {}
							)

							__UpperCAmelCase						:    Any				      =False
							__UpperCAmelCase						:    Optional[int]				      =False
							__UpperCAmelCase						:    str				      =False

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

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

							@unittest.skip(reason="DPT does not use inputs_embeds"	)
							def 			snake_case				(     self	):
										pass

							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	)
													self.assertIsInstance(model.get_input_embeddings()    ,   (nn.Module)	)
													__lowerCAmelCase				    =			model.get_output_embeddings()
													self.assertTrue(x is None or isinstance(__a    ,   nn.Linear	)	)

							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.forward	)
													# 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				    =			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_depth_estimation(*__a	)

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

							def 			snake_case				(     self	):
										for model_class in self.all_model_classes:
													if model_class.__name__ == "DPTForDepthEstimation":
																continue

													__lowerCAmelCase    ,	__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs_for_common()
													__lowerCAmelCase				    =			True

													if model_class in get_values(__a	):
																continue

													__lowerCAmelCase				    =			model_class(__a	)
													model.to(__a	)
													model.train()
													__lowerCAmelCase				    =			self._prepare_for_class(__a    ,   __a    ,   return_labels=__a	)
													__lowerCAmelCase				    =			model(**__a	).loss
													loss.backward()

							def 			snake_case				(     self	):
										for model_class in self.all_model_classes:
													if model_class.__name__ == "DPTForDepthEstimation":
																continue

													__lowerCAmelCase    ,	__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs_for_common()
													__lowerCAmelCase				    =			False
													__lowerCAmelCase				    =			True

													if model_class in get_values(__a	) or not model_class.supports_gradient_checkpointing:
																continue
													__lowerCAmelCase				    =			model_class(__a	)
													model.to(__a	)
													model.gradient_checkpointing_enable()
													model.train()
													__lowerCAmelCase				    =			self._prepare_for_class(__a    ,   __a    ,   return_labels=__a	)
													__lowerCAmelCase				    =			model(**__a	).loss
													loss.backward()

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

										__lowerCAmelCase				    =			_config_zero_init(__a	)
										for model_class in self.all_model_classes:
													__lowerCAmelCase				    =			model_class(config=__a	)
													# Skip the check for the backbone
													__lowerCAmelCase				    =			[]
													for name, module in model.named_modules():
																if module.__class__.__name__ == "DPTViTHybridEmbeddings":
																			__lowerCAmelCase				    =			[f"{name}.{key}" for key in module.state_dict().keys()]
																			break

													for name, param in model.named_parameters():
																if param.requires_grad:
																			if name in backbone_params:
																						continue
																			self.assertIn(
																			    ((param.data.mean() * 1e9).round() / 1e9).item()    ,   [0.0, 1.0]    ,   msg=f"Parameter {name} of model {model_class} seems not properly initialized"    ,   )

							@unittest.skip("Will be fixed soon by reducing the size of the model used for common tests."	)
							def 			snake_case				(     self	):
										pass

							@slow
							def 			snake_case				(     self	):
										for model_name in DPT_PRETRAINED_MODEL_ARCHIVE_LIST[1:]:
													__lowerCAmelCase				    =			DPTModel.from_pretrained(__a	)
													self.assertIsNotNone(__a	)



							def 			snake_case				(     self	):
										# We do this test only for DPTForDepthEstimation since it is the only model that uses readout_type
										__lowerCAmelCase    ,	__lowerCAmelCase				    =			self.model_tester.prepare_config_and_inputs_for_common()
										__lowerCAmelCase				    =			"add"
										with self.assertRaises(__a	):
													__lowerCAmelCase				    =			DPTForDepthEstimation(__a	)


def _lowerCamelCase	(		):

			'''simple docstring'''




			__lowerCAmelCase				    =			Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"      )
			return image


@require_torch
@require_vision
@slow
class   _UpperCamelCase  (   unittest.TestCase		):
							'''simple docstring'''







							def 			snake_case				(     self	):
										__lowerCAmelCase				    =			DPTImageProcessor.from_pretrained("Intel/dpt-hybrid-midas"	)
										__lowerCAmelCase				    =			DPTForDepthEstimation.from_pretrained("Intel/dpt-hybrid-midas"	).to(__a	)

										__lowerCAmelCase				    =			prepare_img()
										__lowerCAmelCase				    =			image_processor(images=__a    ,   return_tensors="pt"	).to(__a	)

										# forward pass
										with torch.no_grad():
													__lowerCAmelCase				    =			model(**__a	)
													__lowerCAmelCase				    =			outputs.predicted_depth

										# verify the predicted depth
										__lowerCAmelCase				    =			torch.Size((1, 3_84, 3_84)	)
										self.assertEqual(predicted_depth.shape    ,   __a	)

										__lowerCAmelCase				    =			torch.tensor(
										    [[[5.6_4_3_7, 5.6_1_4_6, 5.6_5_1_1], [5.4_3_7_1, 5.5_6_4_9, 5.5_9_5_8], [5.5_2_1_5, 5.5_1_8_4, 5.5_2_9_3]]]	).to(__a	)

										self.assertTrue(torch.allclose(outputs.predicted_depth[:3, :3, :3] / 1_00    ,   __a    ,   atol=1e-4	)	)








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




