






"""simple docstring"""





import inspect
import unittest

from transformers import ConvNextVaConfig
from transformers.models.auto import get_values
from transformers.models.auto.modeling_auto import MODEL_FOR_BACKBONE_MAPPING_NAMES, MODEL_MAPPING_NAMES
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

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 ConvNextVaBackbone, ConvNextVaForImageClassification, ConvNextVaModel
  from transformers.models.convnextva.modeling_convnextva import CONVNEXTV2_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
  from PIL import Image

  from transformers import AutoImageProcessor
class    __lowerCamelCase    :

   def __init__(					self ,				snake_case_ ,				snake_case_=13 ,				snake_case_=32 ,				snake_case_=3 ,				snake_case_=4 ,				snake_case_=[10, 20, 30, 40] ,				snake_case_=[2, 2, 3, 2] ,				snake_case_=True ,				snake_case_=True ,				snake_case_=37 ,				snake_case_="gelu" ,				snake_case_=10 ,				snake_case_=0.02 ,				snake_case_=["stage2", "stage3", "stage4"] ,				snake_case_=[2, 3, 4] ,				snake_case_=None ,				)		->       Optional[Any]:
       UpperCamelCase__         =    parent
       UpperCamelCase__         =    batch_size
       UpperCamelCase__         =    image_size
       UpperCamelCase__         =    num_channels
       UpperCamelCase__         =    num_stages
       UpperCamelCase__         =    hidden_sizes
       UpperCamelCase__         =    depths
       UpperCamelCase__         =    is_training
       UpperCamelCase__         =    use_labels
       UpperCamelCase__         =    intermediate_size
       UpperCamelCase__         =    hidden_act
       UpperCamelCase__         =    num_labels
       UpperCamelCase__         =    initializer_range
       UpperCamelCase__         =    out_features
       UpperCamelCase__         =    out_indices
       UpperCamelCase__         =    scope

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]      )

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

       UpperCamelCase__         =    self.get_config()

       return config, pixel_values, labels

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       return ConvNextVaConfig(
           num_channels=self.num_channels ,				hidden_sizes=self.hidden_sizes ,				depths=self.depths ,				num_stages=self.num_stages ,				hidden_act=self.hidden_act ,				is_decoder=snake_case_ ,				initializer_range=self.initializer_range ,				out_features=self.out_features ,				out_indices=self.out_indices ,				num_labels=self.num_labels ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       str:
       UpperCamelCase__         =    ConvNextVaModel(config=snake_case_      )
       model.to(snake_case_      )
       model.eval()
       UpperCamelCase__         =    model(snake_case_      )
       # expected last hidden states: B, C, H // 32, W // 32
       self.parent.assertEqual(
           result.last_hidden_state.shape ,				(self.batch_size, self.hidden_sizes[-1], self.image_size // 32, self.image_size // 32) ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       List[str]:
       UpperCamelCase__         =    ConvNextVaForImageClassification(snake_case_      )
       model.to(snake_case_      )
       model.eval()
       UpperCamelCase__         =    model(snake_case_ ,				labels=snake_case_      )
       self.parent.assertEqual(result.logits.shape ,				(self.batch_size, self.num_labels)      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Union[str, Any]:
       UpperCamelCase__         =    ConvNextVaBackbone(config=snake_case_      )
       model.to(snake_case_      )
       model.eval()
       UpperCamelCase__         =    model(snake_case_      )

       # verify hidden states
       self.parent.assertEqual(len(result.feature_maps      ) ,				len(config.out_features      )      )
       self.parent.assertListEqual(list(result.feature_maps[0].shape      ) ,				[self.batch_size, self.hidden_sizes[1], 4, 4]      )

       # verify channels
       self.parent.assertEqual(len(model.channels      ) ,				len(config.out_features      )      )
       self.parent.assertListEqual(model.channels ,				config.hidden_sizes[1:]      )

       # verify backbone works with out_features=None
       UpperCamelCase__         =    None
       UpperCamelCase__         =    ConvNextVaBackbone(config=snake_case_      )
       model.to(snake_case_      )
       model.eval()
       UpperCamelCase__         =    model(snake_case_      )

       # verify feature maps
       self.parent.assertEqual(len(result.feature_maps      ) ,				1      )
       self.parent.assertListEqual(list(result.feature_maps[0].shape      ) ,				[self.batch_size, self.hidden_sizes[-1], 1, 1]      )

       # verify channels
       self.parent.assertEqual(len(model.channels      ) ,				1      )
       self.parent.assertListEqual(model.channels ,				[config.hidden_sizes[-1]]      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       UpperCamelCase__         =    self.prepare_config_and_inputs()
       UpperCamelCase__         =    config_and_inputs
       UpperCamelCase__         =    {"pixel_values": pixel_values}
       return config, inputs_dict







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    self.prepare_config_and_inputs()
       UpperCamelCase__         =    config_and_inputs
       UpperCamelCase__         =    {"pixel_values": pixel_values, "labels": labels}
       return config, inputs_dict







@require_torch
class    __lowerCamelCase    (  _UpperCamelCase							,	_UpperCamelCase							,	unittest.TestCase  ):
   a      :				Union[str, Any] 						=(
       (
           ConvNextVaModel,
           ConvNextVaForImageClassification,
           ConvNextVaBackbone,
       )
       if is_torch_available()
       else ()
   )
   a      :				Tuple 						=(
       {"""feature-extraction""": ConvNextVaModel, """image-classification""": ConvNextVaForImageClassification}
       if is_torch_available()
       else {}
   )

   a      :				List[str] 						=False
   a      :				Optional[Any] 						=False
   a      :				List[Any] 						=False
   a      :				str 						=False
   a      :				Optional[int] 						=False

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       str:
       UpperCamelCase__         =    ConvNextVaModelTester(self      )
       UpperCamelCase__         =    ConfigTester(self ,				config_class=snake_case_ ,				has_text_modality=snake_case_ ,				hidden_size=37      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       self.create_and_test_config_common_properties()
       self.config_tester.create_and_test_config_to_json_string()
       self.config_tester.create_and_test_config_to_json_file()
       self.config_tester.create_and_test_config_from_and_save_pretrained()
       self.config_tester.create_and_test_config_with_num_labels()
       self.config_tester.check_config_can_be_init_without_params()
       self.config_tester.check_config_arguments_init()

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       return

   @unittest.skip(reason='ConvNextV2 does not use inputs_embeds'      )
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       pass

   @unittest.skip(reason='ConvNextV2 does not support input and output embeddings'      )
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       pass

   @unittest.skip(reason='ConvNextV2 does not use feedforward chunking'      )
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       pass

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       if not self.model_tester.is_training:
           return

       for model_class in self.all_model_classes:
           UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs_with_labels()
           UpperCamelCase__         =    True

           if model_class.__name__ in [
               *get_values(snake_case_      ),
               *get_values(snake_case_      ),
           ]:
               continue

           UpperCamelCase__         =    model_class(snake_case_      )
           model.to(snake_case_      )
           model.train()
           UpperCamelCase__         =    self._prepare_for_class(snake_case_ ,				snake_case_ ,				return_labels=snake_case_      )
           UpperCamelCase__         =    model(**snake_case_      ).loss
           loss.backward()

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       if not self.model_tester.is_training:
           return

       for model_class in self.all_model_classes:
           UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs_with_labels()
           UpperCamelCase__         =    False
           UpperCamelCase__         =    True

           if (
               model_class.__name__
               in [*get_values(snake_case_      ), *get_values(snake_case_      )]
               or not model_class.supports_gradient_checkpointing
           ):
               continue

           UpperCamelCase__         =    model_class(snake_case_      )
           model.to(snake_case_      )
           model.gradient_checkpointing_enable()
           model.train()
           UpperCamelCase__         =    self._prepare_for_class(snake_case_ ,				snake_case_ ,				return_labels=snake_case_      )
           UpperCamelCase__         =    model(**snake_case_      ).loss
           loss.backward()

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs_for_common()

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

           UpperCamelCase__         =    ["pixel_values"]
           self.assertListEqual(arg_names[:1] ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_model(*snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       def check_hidden_states_output(snake_case_ ,				snake_case_ ,				snake_case_      ):
           UpperCamelCase__         =    model_class(snake_case_      )
           model.to(snake_case_      )
           model.eval()

           with torch.no_grad():
               UpperCamelCase__         =    model(**self._prepare_for_class(snake_case_ ,				snake_case_      )      )

           UpperCamelCase__         =    outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

           UpperCamelCase__         =    self.model_tester.num_stages
           self.assertEqual(len(snake_case_      ) ,				expected_num_stages + 1      )

           # ConvNextV2's feature maps are of shape (batch_size, num_channels, height, width)
           self.assertListEqual(
               list(hidden_states[0].shape[-2:]      ) ,				[self.model_tester.image_size // 4, self.model_tester.image_size // 4] ,				)

       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs_for_common()

       for model_class in self.all_model_classes:
           UpperCamelCase__         =    True
           check_hidden_states_output(snake_case_ ,				snake_case_ ,				snake_case_      )

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

           check_hidden_states_output(snake_case_ ,				snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    self.model_tester.prepare_config_and_inputs()
       self.model_tester.create_and_check_for_image_classification(*snake_case_      )







   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       for model_name in CONVNEXTV2_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
           UpperCamelCase__         =    ConvNextVaModel.from_pretrained(snake_case_      )
           self.assertIsNotNone(snake_case_      )







def 	lowerCAmelCase_( )					->	Union[str, Any]:
    """simple docstring"""

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





@require_torch
@require_vision
class    __lowerCamelCase    (  unittest.TestCase  ):

   @cached_property
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       return AutoImageProcessor.from_pretrained('facebook/convnextv2-tiny-1k-224'      ) if is_vision_available() else None







   @slow
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    ConvNextVaForImageClassification.from_pretrained('facebook/convnextv2-tiny-1k-224'      ).to(snake_case_      )

       UpperCamelCase__         =    self.default_image_processor
       UpperCamelCase__         =    prepare_img()
       UpperCamelCase__         =    preprocessor(images=snake_case_ ,				return_tensors='pt'      ).to(snake_case_      )

       # forward pass
       with torch.no_grad():
           UpperCamelCase__         =    model(**snake_case_      )

       # verify the logits
       UpperCamelCase__         =    torch.Size((1, 1000)      )
       self.assertEqual(outputs.logits.shape ,				snake_case_      )

       UpperCamelCase__         =    torch.tensor([0.9_996, 0.1_966, -0.4_386]      ).to(snake_case_      )
       self.assertTrue(torch.allclose(outputs.logits[0, :3] ,				snake_case_ ,				atol=1E-4      )      )












"""simple docstring"""





import sys
from collections import defaultdict
class    __lowerCamelCase    :

   def __init__(					self      )		->       Tuple:
       UpperCamelCase__         =    []

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

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Optional[int]:
       UpperCamelCase__         =    pos

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       List[Any]:
       if start > size // 2 - 1:
           return
       else:
           if 2 * start + 2 >= size:
               UpperCamelCase__         =    2 * start + 1
           else:
               if heap[2 * start + 1] < heap[2 * start + 2]:
                   UpperCamelCase__         =    2 * start + 1
               else:
                   UpperCamelCase__         =    2 * start + 2
           if heap[smallest_child] < heap[start]:
               UpperCamelCase__       ,						UpperCamelCase__         =    heap[smallest_child], positions[smallest_child]
               UpperCamelCase__       ,						UpperCamelCase__         =    (
                   heap[start],
                   positions[start],
               )
               UpperCamelCase__       ,						UpperCamelCase__         =    temp, tempa

               UpperCamelCase__         =    self.get_position(positions[smallest_child]      )
               self.set_position(
                   positions[smallest_child] ,				self.get_position(positions[start]      )      )
               self.set_position(positions[start] ,				snake_case_      )

               self.top_to_bottom(snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       Any:
       UpperCamelCase__         =    position[index]

       while index != 0:
           UpperCamelCase__         =    int((index - 2) / 2      ) if index % 2 == 0 else int((index - 1) / 2      )

           if val < heap[parent]:
               UpperCamelCase__         =    heap[parent]
               UpperCamelCase__         =    position[parent]
               self.set_position(position[parent] ,				snake_case_      )
           else:
               UpperCamelCase__         =    val
               UpperCamelCase__         =    temp
               self.set_position(snake_case_ ,				snake_case_      )
               break
           UpperCamelCase__         =    parent
       else:
           UpperCamelCase__         =    val
           UpperCamelCase__         =    temp
           self.set_position(snake_case_ ,				0      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       Any:
       UpperCamelCase__         =    len(snake_case_      ) // 2 - 1
       for i in range(snake_case_ ,				-1 ,				-1      ):
           self.top_to_bottom(snake_case_ ,				snake_case_ ,				len(snake_case_      ) ,				snake_case_      )







   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       List[Any]:
       UpperCamelCase__         =    positions[0]
       UpperCamelCase__         =    sys.maxsize
       self.top_to_bottom(snake_case_ ,				0 ,				len(snake_case_      ) ,				snake_case_      )
       return temp







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE					)					->	Tuple:
    """simple docstring"""

    UpperCamelCase__         =    Heap()

    UpperCamelCase__         =    [0] * len(SCREAMING_SNAKE_CASE					)
    UpperCamelCase__         =    [-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
    UpperCamelCase__         =    []  # Heap of Distance of vertices from their neighboring vertex
    UpperCamelCase__         =    []

    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					)

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

    for _ in range(1 ,	len(SCREAMING_SNAKE_CASE					)					):
        UpperCamelCase__         =    heap.delete_minimum(SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)
        if visited[vertex] == 0:
            tree_edges.append((nbr_tv[vertex], vertex)					)
            UpperCamelCase__         =    1
            for neighbor, distance in adjacency_list[vertex]:
                if (
                    visited[neighbor] == 0
                    and distance < distance_tv[heap.get_position(SCREAMING_SNAKE_CASE					)]
                ):
                    UpperCamelCase__         =    distance
                    heap.bottom_to_top(
                        SCREAMING_SNAKE_CASE ,	heap.get_position(SCREAMING_SNAKE_CASE					) ,	SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)
                    UpperCamelCase__         =    vertex
    return tree_edges


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




