




'''simple docstring'''


import inspect
import unittest

from transformers import SegformerConfig, is_torch_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device

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


if is_torch_available():
				import torch

				from transformers import (
				    MODEL_MAPPING,
				    SegformerForImageClassification,
				    SegformerForSemanticSegmentation,
				    SegformerModel,
				)
				from transformers.models.segformer.modeling_segformer import SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
				from PIL import Image

				from transformers import SegformerImageProcessor

class     A					(	_a					):







							def      __lowerCAmelCase    (						self :						List[Any]      )    ->							List[Any]:


														"""simple docstring"""


														_a			  =       self.config_class(**self.inputs_dict      )
														self.parent.assertTrue(hasattr(lowerCAmelCase_							,    '''hidden_sizes'''      )      )
														self.parent.assertTrue(hasattr(lowerCAmelCase_							,    '''num_attention_heads'''      )      )
														self.parent.assertTrue(hasattr(lowerCAmelCase_							,    '''num_encoder_blocks'''      )      )



class     A					:







							def __init__(						self :						List[Any]							,    lowerCAmelCase_ :						Tuple							,    lowerCAmelCase_ :						Optional[Any]=13							,    lowerCAmelCase_ :						Optional[int]=64							,    lowerCAmelCase_ :						Union[str, Any]=3							,    lowerCAmelCase_ :						Tuple=4							,    lowerCAmelCase_ :						List[str]=[2, 2, 2, 2]							,    lowerCAmelCase_ :						Tuple=[8, 4, 2, 1]							,    lowerCAmelCase_ :						Dict=[16, 32, 64, 1_28]							,    lowerCAmelCase_ :						Any=[1, 4, 8, 16]							,    lowerCAmelCase_ :						str=[1, 2, 4, 8]							,    lowerCAmelCase_ :						Any=True							,    lowerCAmelCase_ :						List[str]=True							,    lowerCAmelCase_ :						Optional[int]="gelu"							,    lowerCAmelCase_ :						Union[str, Any]=0.1							,    lowerCAmelCase_ :						str=0.1							,    lowerCAmelCase_ :						Optional[int]=0.0_2							,    lowerCAmelCase_ :						Tuple=3							,    lowerCAmelCase_ :						List[Any]=None							,    )    ->							List[str]:


														"""simple docstring"""


														_a			  =       parent
														_a			  =       batch_size
														_a			  =       image_size
														_a			  =       num_channels
														_a			  =       num_encoder_blocks
														_a			  =       sr_ratios
														_a			  =       depths
														_a			  =       hidden_sizes
														_a			  =       downsampling_rates
														_a			  =       num_attention_heads
														_a			  =       is_training
														_a			  =       use_labels
														_a			  =       hidden_act
														_a			  =       hidden_dropout_prob
														_a			  =       attention_probs_dropout_prob
														_a			  =       initializer_range
														_a			  =       num_labels
														_a			  =       scope







							def      __lowerCAmelCase    (						self :						Tuple      )    ->							List[str]:


														"""simple docstring"""


														_a			  =       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]      )

														_a			  =       None
														if self.use_labels:
																					_a			  =       ids_tensor([self.batch_size, self.image_size, self.image_size]							,    self.num_labels      )

														_a			  =       self.get_config()
														return config, pixel_values, labels







							def      __lowerCAmelCase    (						self :						Union[str, Any]      )    ->							Union[str, Any]:


														"""simple docstring"""


														return SegformerConfig(
														    image_size=self.image_size							,    num_channels=self.num_channels							,    num_encoder_blocks=self.num_encoder_blocks							,    depths=self.depths							,    hidden_sizes=self.hidden_sizes							,    num_attention_heads=self.num_attention_heads							,    hidden_act=self.hidden_act							,    hidden_dropout_prob=self.hidden_dropout_prob							,    attention_probs_dropout_prob=self.attention_probs_dropout_prob							,    initializer_range=self.initializer_range							,    )







							def      __lowerCAmelCase    (						self :						Tuple							,    lowerCAmelCase_ :						Tuple							,    lowerCAmelCase_ :						str							,    lowerCAmelCase_ :						Optional[int]      )    ->							str:


														"""simple docstring"""


														_a			  =       SegformerModel(config=lowerCAmelCase_      )
														model.to(lowerCAmelCase_      )
														model.eval()
														_a			  =       model(lowerCAmelCase_      )
														_a			  =       _a			  =       self.image_size // (self.downsampling_rates[-1] * 2)
														self.parent.assertEqual(
														    result.last_hidden_state.shape							,    (self.batch_size, self.hidden_sizes[-1], expected_height, expected_width)      )







							def      __lowerCAmelCase    (						self :						List[str]							,    lowerCAmelCase_ :						Optional[Any]							,    lowerCAmelCase_ :						Union[str, Any]							,    lowerCAmelCase_ :						List[str]      )    ->							Optional[Any]:


														"""simple docstring"""


														_a			  =       self.num_labels
														_a			  =       SegformerForSemanticSegmentation(lowerCAmelCase_      )
														model.to(lowerCAmelCase_      )
														model.eval()
														_a			  =       model(lowerCAmelCase_      )
														self.parent.assertEqual(
														    result.logits.shape							,    (self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4)      )
														_a			  =       model(lowerCAmelCase_							,    labels=lowerCAmelCase_      )
														self.parent.assertEqual(
														    result.logits.shape							,    (self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4)      )
														self.parent.assertGreater(result.loss							,    0.0      )







							def      __lowerCAmelCase    (						self :						Union[str, Any]							,    lowerCAmelCase_ :						Union[str, Any]							,    lowerCAmelCase_ :						List[str]							,    lowerCAmelCase_ :						Dict      )    ->							Dict:


														"""simple docstring"""


														_a			  =       1
														_a			  =       SegformerForSemanticSegmentation(config=lowerCAmelCase_      )
														model.to(lowerCAmelCase_      )
														model.eval()
														_a			  =       torch.randint(0							,    1							,    (self.batch_size, self.image_size, self.image_size)      ).to(lowerCAmelCase_      )
														_a			  =       model(lowerCAmelCase_							,    labels=lowerCAmelCase_      )
														self.parent.assertGreater(result.loss							,    0.0      )







							def      __lowerCAmelCase    (						self :						List[Any]      )    ->							Optional[Any]:


														"""simple docstring"""


														_a			  =       self.prepare_config_and_inputs()
														_a  ,							_a  ,							_a			  =       config_and_inputs
														_a			  =       {'''pixel_values''': pixel_values}
														return config, inputs_dict



@require_torch
class     A					(	_a  ,_a  ,unittest.TestCase					):
							lowercase_           =       (
							    (
							        SegformerModel,
							        SegformerForSemanticSegmentation,
							        SegformerForImageClassification,
							    )
							    if is_torch_available()
							    else ()
							)
							lowercase_           =       (
							    {
							        'feature-extraction': SegformerModel,
							        'image-classification': SegformerForImageClassification,
							        'image-segmentation': SegformerForSemanticSegmentation,
							    }
							    if is_torch_available()
							    else {}
							)

							lowercase_           =       True
							lowercase_           =       False
							lowercase_           =       False
							lowercase_           =       False







							def      __lowerCAmelCase    (						self :						Union[str, Any]      )    ->							str:


														"""simple docstring"""


														_a			  =       SegformerModelTester(self      )
														_a			  =       SegformerConfigTester(self							,    config_class=lowerCAmelCase_      )







							def      __lowerCAmelCase    (						self :						str      )    ->							Tuple:


														"""simple docstring"""


														self.config_tester.run_common_tests()







							def      __lowerCAmelCase    (						self :						Union[str, Any]      )    ->							Any:


														"""simple docstring"""


														_a			  =       self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_model(*lowerCAmelCase_      )







							def      __lowerCAmelCase    (						self :						str      )    ->							Any:


														"""simple docstring"""


														_a			  =       self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_for_binary_image_segmentation(*lowerCAmelCase_      )







							def      __lowerCAmelCase    (						self :						Optional[Any]      )    ->							Union[str, Any]:


														"""simple docstring"""


														_a			  =       self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_for_image_segmentation(*lowerCAmelCase_      )







							@unittest.skip('''SegFormer does not use inputs_embeds'''      )
							def      __lowerCAmelCase    (						self :						Optional[int]      )    ->							Optional[int]:


														"""simple docstring"""


														pass







							@unittest.skip('''SegFormer does not have get_input_embeddings method and get_output_embeddings methods'''      )
							def      __lowerCAmelCase    (						self :						Dict      )    ->							List[str]:


														"""simple docstring"""


														pass







							def      __lowerCAmelCase    (						self :						List[str]      )    ->							int:


														"""simple docstring"""


														_a  ,							_a			  =       self.model_tester.prepare_config_and_inputs_for_common()

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

																					_a			  =       ['''pixel_values''']
																					self.assertListEqual(arg_names[:1]							,    lowerCAmelCase_      )







							def      __lowerCAmelCase    (						self :						Any      )    ->							List[Any]:


														"""simple docstring"""


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

														for model_class in self.all_model_classes:
																					_a			  =       True
																					_a			  =       False
																					_a			  =       True
																					_a			  =       model_class(lowerCAmelCase_      )
																					model.to(lowerCAmelCase_      )
																					model.eval()
																					with torch.no_grad():
																												_a			  =       model(**self._prepare_for_class(lowerCAmelCase_							,    lowerCAmelCase_      )      )
																					_a			  =       outputs.attentions

																					_a			  =       sum(self.model_tester.depths      )
																					self.assertEqual(len(lowerCAmelCase_      )							,    lowerCAmelCase_      )

																					# check that output_attentions also work using config
																					del inputs_dict["output_attentions"]
																					_a			  =       True
																					_a			  =       model_class(lowerCAmelCase_      )
																					model.to(lowerCAmelCase_      )
																					model.eval()
																					with torch.no_grad():
																												_a			  =       model(**self._prepare_for_class(lowerCAmelCase_							,    lowerCAmelCase_      )      )
																					_a			  =       outputs.attentions

																					self.assertEqual(len(lowerCAmelCase_      )							,    lowerCAmelCase_      )

																					# verify the first attentions (first block, first layer)
																					_a			  =       (self.model_tester.image_size // 4) ** 2
																					_a			  =       (self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
																					self.assertListEqual(
																					    list(attentions[0].shape[-3:]      )							,    [self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]							,    )

																					# verify the last attentions (last block, last layer)
																					_a			  =       (self.model_tester.image_size // 32) ** 2
																					_a			  =       (self.model_tester.image_size // (32 * self.model_tester.sr_ratios[-1])) ** 2
																					self.assertListEqual(
																					    list(attentions[-1].shape[-3:]      )							,    [self.model_tester.num_attention_heads[-1], expected_seq_len, expected_reduced_seq_len]							,    )
																					_a			  =       len(lowerCAmelCase_      )

																					# Check attention is always last and order is fine
																					_a			  =       True
																					_a			  =       True
																					_a			  =       model_class(lowerCAmelCase_      )
																					model.to(lowerCAmelCase_      )
																					model.eval()
																					with torch.no_grad():
																												_a			  =       model(**self._prepare_for_class(lowerCAmelCase_							,    lowerCAmelCase_      )      )

																					self.assertEqual(out_len + 1							,    len(lowerCAmelCase_      )      )

																					_a			  =       outputs.attentions

																					self.assertEqual(len(lowerCAmelCase_      )							,    lowerCAmelCase_      )
																					# verify the first attentions (first block, first layer)
																					_a			  =       (self.model_tester.image_size // 4) ** 2
																					_a			  =       (self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
																					self.assertListEqual(
																					    list(self_attentions[0].shape[-3:]      )							,    [self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]							,    )







							def      __lowerCAmelCase    (						self :						str      )    ->							Any:


														"""simple docstring"""


														def check_hidden_states_output(lowerCAmelCase_ :						Union[str, Any]							,    lowerCAmelCase_ :						Tuple							,    lowerCAmelCase_ :						int      ):
																					_a			  =       model_class(lowerCAmelCase_      )
																					model.to(lowerCAmelCase_      )
																					model.eval()

																					with torch.no_grad():
																												_a			  =       model(**self._prepare_for_class(lowerCAmelCase_							,    lowerCAmelCase_      )      )

																					_a			  =       outputs.hidden_states

																					_a			  =       self.model_tester.num_encoder_blocks
																					self.assertEqual(len(lowerCAmelCase_      )							,    lowerCAmelCase_      )

																					# verify the first hidden states (first block)
																					self.assertListEqual(
																					    list(hidden_states[0].shape[-3:]      )							,    [
																					        self.model_tester.hidden_sizes[0],
																					        self.model_tester.image_size // 4,
																					        self.model_tester.image_size // 4,
																					    ]							,    )

														_a  ,							_a			  =       self.model_tester.prepare_config_and_inputs_for_common()

														for model_class in self.all_model_classes:
																					_a			  =       True
																					check_hidden_states_output(lowerCAmelCase_							,    lowerCAmelCase_							,    lowerCAmelCase_      )

																					# check that output_hidden_states also work using config
																					del inputs_dict["output_hidden_states"]
																					_a			  =       True

																					check_hidden_states_output(lowerCAmelCase_							,    lowerCAmelCase_							,    lowerCAmelCase_      )







							def      __lowerCAmelCase    (						self :						Optional[Any]      )    ->							Optional[int]:


														"""simple docstring"""


														if not self.model_tester.is_training:
																					return

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

														for model_class in self.all_model_classes:
																					if model_class in get_values(lowerCAmelCase_      ):
																												continue

																					_a			  =       model_class(lowerCAmelCase_      )
																					model.to(lowerCAmelCase_      )
																					model.train()
																					_a			  =       self._prepare_for_class(lowerCAmelCase_							,    lowerCAmelCase_							,    return_labels=lowerCAmelCase_      )
																					_a			  =       model(**lowerCAmelCase_      ).loss
																					loss.backward()







							@unittest.skip('''Will be fixed soon by reducing the size of the model used for common tests.'''      )
							def      __lowerCAmelCase    (						self :						Tuple      )    ->							str:


														"""simple docstring"""


														pass







							@slow
							def      __lowerCAmelCase    (						self :						List[str]      )    ->							Tuple:


														"""simple docstring"""


														for model_name in SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																					_a			  =       SegformerModel.from_pretrained(lowerCAmelCase_      )
																					self.assertIsNotNone(lowerCAmelCase_      )



def 	snake_case_					():





							'''simple docstring'''


							_a			  =       Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''   )
							return image

@require_torch
class     A					(	unittest.TestCase					):







							@slow
							def      __lowerCAmelCase    (						self :						Optional[int]      )    ->							str:


														"""simple docstring"""


														_a			  =       SegformerImageProcessor(
														    image_scale=(5_12, 5_12)							,    keep_ratio=lowerCAmelCase_							,    align=lowerCAmelCase_							,    do_random_crop=lowerCAmelCase_      )
														_a			  =       SegformerForSemanticSegmentation.from_pretrained('''nvidia/segformer-b0-finetuned-ade-512-512'''      ).to(
														    lowerCAmelCase_      )

														_a			  =       prepare_img()
														_a			  =       image_processor(images=lowerCAmelCase_							,    return_tensors='''pt'''      )
														_a			  =       encoded_inputs.pixel_values.to(lowerCAmelCase_      )

														with torch.no_grad():
																					_a			  =       model(lowerCAmelCase_      )

														_a			  =       torch.Size((1, model.config.num_labels, 1_28, 1_28)      )
														self.assertEqual(outputs.logits.shape							,    lowerCAmelCase_      )

														_a			  =       torch.tensor(
														    [
														        [[-4.6_3_1_0, -5.5_2_3_2, -6.2_3_5_6], [-5.1_9_2_1, -6.1_4_4_4, -6.5_9_9_6], [-5.4_4_2_4, -6.2_7_9_0, -6.7_5_7_4]],
														        [[-1_2.1_3_9_1, -1_3.3_1_2_2, -1_3.9_5_5_4], [-1_2.8_7_3_2, -1_3.9_3_5_2, -1_4.3_5_6_3], [-1_2.9_4_3_8, -1_3.8_2_2_6, -1_4.2_5_1_3]],
														        [[-1_2.5_1_3_4, -1_3.4_6_8_6, -1_4.4_9_1_5], [-1_2.8_6_6_9, -1_4.4_3_4_3, -1_4.7_7_5_8], [-1_3.2_5_2_3, -1_4.5_8_1_9, -1_5.0_6_9_4]],
														    ]      ).to(lowerCAmelCase_      )
														self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3]							,    lowerCAmelCase_							,    atol=1e-4      )      )







							@slow
							def      __lowerCAmelCase    (						self :						int      )    ->							List[str]:


														"""simple docstring"""


														_a			  =       SegformerImageProcessor(
														    image_scale=(5_12, 5_12)							,    keep_ratio=lowerCAmelCase_							,    align=lowerCAmelCase_							,    do_random_crop=lowerCAmelCase_      )
														_a			  =       SegformerForSemanticSegmentation.from_pretrained(
														    '''nvidia/segformer-b1-finetuned-cityscapes-1024-1024'''      ).to(lowerCAmelCase_      )

														_a			  =       prepare_img()
														_a			  =       image_processor(images=lowerCAmelCase_							,    return_tensors='''pt'''      )
														_a			  =       encoded_inputs.pixel_values.to(lowerCAmelCase_      )

														with torch.no_grad():
																					_a			  =       model(lowerCAmelCase_      )

														_a			  =       torch.Size((1, model.config.num_labels, 1_28, 1_28)      )
														self.assertEqual(outputs.logits.shape							,    lowerCAmelCase_      )

														_a			  =       torch.tensor(
														    [
														        [[-1_3.5_7_4_8, -1_3.9_1_1_1, -1_2.6_5_0_0], [-1_4.3_5_0_0, -1_5.3_6_8_3, -1_4.2_3_2_8], [-1_4.7_5_3_2, -1_6.0_4_2_4, -1_5.6_0_8_7]],
														        [[-1_7.1_6_5_1, -1_5.8_7_2_5, -1_2.9_6_5_3], [-1_7.2_5_8_0, -1_7.3_7_1_8, -1_4.8_2_2_3], [-1_6.6_0_5_8, -1_6.8_7_8_3, -1_6.7_4_5_2]],
														        [[-3.6_4_5_6, -3.0_2_0_9, -1.4_2_0_3], [-3.0_7_9_7, -3.1_9_5_9, -2.0_0_0_0], [-1.8_7_5_7, -1.9_2_1_7, -1.6_9_9_7]],
														    ]      ).to(lowerCAmelCase_      )
														self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3]							,    lowerCAmelCase_							,    atol=1e-1      )      )







							@slow
							def      __lowerCAmelCase    (						self :						Optional[Any]      )    ->							str:


														"""simple docstring"""


														_a			  =       SegformerImageProcessor(
														    image_scale=(5_12, 5_12)							,    keep_ratio=lowerCAmelCase_							,    align=lowerCAmelCase_							,    do_random_crop=lowerCAmelCase_      )
														_a			  =       SegformerForSemanticSegmentation.from_pretrained('''nvidia/segformer-b0-finetuned-ade-512-512'''      ).to(
														    lowerCAmelCase_      )

														_a			  =       prepare_img()
														_a			  =       image_processor(images=lowerCAmelCase_							,    return_tensors='''pt'''      )
														_a			  =       encoded_inputs.pixel_values.to(lowerCAmelCase_      )

														with torch.no_grad():
																					_a			  =       model(lowerCAmelCase_      )

														_a			  =       outputs.logits.detach().cpu()

														_a			  =       image_processor.post_process_semantic_segmentation(outputs=lowerCAmelCase_							,    target_sizes=[(5_00, 3_00)]      )
														_a			  =       torch.Size((5_00, 3_00)      )
														self.assertEqual(segmentation[0].shape							,    lowerCAmelCase_      )

														_a			  =       image_processor.post_process_semantic_segmentation(outputs=lowerCAmelCase_      )
														_a			  =       torch.Size((1_28, 1_28)      )
														self.assertEqual(segmentation[0].shape							,    lowerCAmelCase_      )







'''simple docstring'''


import sys
from collections import defaultdict

class     A					:







							def __init__(						self :						Optional[Any]      )    ->							Union[str, Any]:


														"""simple docstring"""


														_a			  =       []







							def      __lowerCAmelCase    (						self :						Union[str, Any]							,    lowerCAmelCase_ :						List[Any]      )    ->							int:


														"""simple docstring"""


														return self.node_position[vertex]







							def      __lowerCAmelCase    (						self :						List[Any]							,    lowerCAmelCase_ :						Optional[Any]							,    lowerCAmelCase_ :						Optional[Any]      )    ->							Tuple:


														"""simple docstring"""


														_a			  =       pos







							def      __lowerCAmelCase    (						self :						Dict							,    lowerCAmelCase_ :						str							,    lowerCAmelCase_ :						Any							,    lowerCAmelCase_ :						Dict							,    lowerCAmelCase_ :						int      )    ->							Any:


														"""simple docstring"""


														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]							,    lowerCAmelCase_      )

																												self.top_to_bottom(lowerCAmelCase_							,    lowerCAmelCase_							,    lowerCAmelCase_							,    lowerCAmelCase_      )







							def      __lowerCAmelCase    (						self :						Optional[int]							,    lowerCAmelCase_ :						List[str]							,    lowerCAmelCase_ :						List[Any]							,    lowerCAmelCase_ :						Any							,    lowerCAmelCase_ :						Dict      )    ->							Any:


														"""simple docstring"""


														_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]							,    lowerCAmelCase_      )
																					else:
																												_a			  =       val
																												_a			  =       temp
																												self.set_position(lowerCAmelCase_							,    lowerCAmelCase_      )
																												break
																					_a			  =       parent
														else:
																					_a			  =       val
																					_a			  =       temp
																					self.set_position(lowerCAmelCase_							,    0      )







							def      __lowerCAmelCase    (						self :						Any							,    lowerCAmelCase_ :						List[Any]							,    lowerCAmelCase_ :						Optional[Any]      )    ->							Optional[int]:


														"""simple docstring"""


														_a			  =       len(lowerCAmelCase_      ) // 2 - 1
														for i in range(lowerCAmelCase_							,    -1							,    -1      ):
																					self.top_to_bottom(lowerCAmelCase_							,    lowerCAmelCase_							,    len(lowerCAmelCase_      )							,    lowerCAmelCase_      )







							def      __lowerCAmelCase    (						self :						str							,    lowerCAmelCase_ :						str							,    lowerCAmelCase_ :						int      )    ->							List[Any]:


														"""simple docstring"""


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



def 	snake_case_					(UpperCamelCase :						Any   ):





							'''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 --------- >
				_snake_case   :   List[str]     							=	int(input('Enter number of edges: ').strip())
				_snake_case   :   Union[str, Any]     							=	defaultdict(list)
				for _ in range(edges_number):
								_snake_case   :   Tuple     							=	[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))

