



'''simple docstring'''






from __future__ import annotations

import inspect
import unittest

import numpy as np

from transformers import SwinConfig
from transformers.testing_utils import require_tf, require_vision, slow, to_atuple
from transformers.utils import cached_property, is_tf_available, is_vision_available

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


if is_tf_available():
   import tensorflow as tf

   from transformers.models.swin.modeling_tf_swin import (
       TF_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST,
       TFSwinForImageClassification,
       TFSwinForMaskedImageModeling,
       TFSwinModel,
   )


if is_vision_available():
   from PIL import Image

   from transformers import AutoImageProcessor



class 				lowercase			:


 """simple docstring"""


 def __init__(				self    ,a_    ,a_=13    ,a_=32    ,a_=2    ,a_=3    ,a_=16    ,a_=[1, 2, 1]    ,a_=[2, 2, 4]    ,a_=2    ,a_=2.0    ,a_=True    ,a_=0.0    ,a_=0.0    ,a_=0.1    ,a_="gelu"    ,a_=False    ,a_=True    ,a_=0.02    ,a_=1E-5    ,a_=True    ,a_=None    ,a_=True    ,a_=10    ,a_=8    ,)						->  None:
        _UpperCAmelCase    :		int     	=					parent
        _UpperCAmelCase    :		Optional[int]     	=					batch_size
        _UpperCAmelCase    :		List[Any]     	=					image_size
        _UpperCAmelCase    :		Optional[int]     	=					patch_size
        _UpperCAmelCase    :		Union[str, Any]     	=					num_channels
        _UpperCAmelCase    :		Tuple     	=					embed_dim
        _UpperCAmelCase    :		Union[str, Any]     	=					depths
        _UpperCAmelCase    :		List[Any]     	=					num_heads
        _UpperCAmelCase    :		Optional[int]     	=					window_size
        _UpperCAmelCase    :		Tuple     	=					mlp_ratio
        _UpperCAmelCase    :		Optional[int]     	=					qkv_bias
        _UpperCAmelCase    :		Union[str, Any]     	=					hidden_dropout_prob
        _UpperCAmelCase    :		str     	=					attention_probs_dropout_prob
        _UpperCAmelCase    :		Optional[int]     	=					drop_path_rate
        _UpperCAmelCase    :		Tuple     	=					hidden_act
        _UpperCAmelCase    :		List[str]     	=					use_absolute_embeddings
        _UpperCAmelCase    :		int     	=					patch_norm
        _UpperCAmelCase    :		str     	=					layer_norm_eps
        _UpperCAmelCase    :		List[Any]     	=					initializer_range
        _UpperCAmelCase    :		Any     	=					is_training
        _UpperCAmelCase    :		Any     	=					scope
        _UpperCAmelCase    :		Optional[Any]     	=					use_labels
        _UpperCAmelCase    :		Dict     	=					type_sequence_label_size
        _UpperCAmelCase    :		str     	=					encoder_stride







 def _snake_case					(				self				)						->  Optional[Any]:
        _UpperCAmelCase    :		Any     	=					floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]				)

        _UpperCAmelCase    :		str     	=					None
        if self.use_labels:
               _UpperCAmelCase    :		Dict     	=					ids_tensor([self.batch_size]    ,self.type_sequence_label_size				)

        _UpperCAmelCase    :		str     	=					self.get_config()

        return config, pixel_values, labels







 def _snake_case					(				self				)						->  Any:
        return SwinConfig(
            image_size=self.image_size    ,patch_size=self.patch_size    ,num_channels=self.num_channels    ,embed_dim=self.embed_dim    ,depths=self.depths    ,num_heads=self.num_heads    ,window_size=self.window_size    ,mlp_ratio=self.mlp_ratio    ,qkv_bias=self.qkv_bias    ,hidden_dropout_prob=self.hidden_dropout_prob    ,attention_probs_dropout_prob=self.attention_probs_dropout_prob    ,drop_path_rate=self.drop_path_rate    ,hidden_act=self.hidden_act    ,use_absolute_embeddings=self.use_absolute_embeddings    ,path_norm=self.patch_norm    ,layer_norm_eps=self.layer_norm_eps    ,initializer_range=self.initializer_range    ,encoder_stride=self.encoder_stride    ,)







 def _snake_case					(				self    ,a_    ,a_    ,a_				)						->  Any:
        _UpperCAmelCase    :		List[str]     	=					TFSwinModel(config=a_				)
        _UpperCAmelCase    :		Optional[int]     	=					model(a_				)

        _UpperCAmelCase    :		Optional[int]     	=					((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths				) - 1))
        _UpperCAmelCase    :		str     	=					int(config.embed_dim * 2 ** (len(config.depths				) - 1)				)

        self.parent.assertEqual(result.last_hidden_state.shape    ,(self.batch_size, expected_seq_len, expected_dim)				)







 def _snake_case					(				self    ,a_    ,a_    ,a_				)						->  Optional[Any]:
        _UpperCAmelCase    :		Optional[Any]     	=					TFSwinForMaskedImageModeling(config=a_				)
        _UpperCAmelCase    :		Any     	=					model(a_				)
        self.parent.assertEqual(
            result.logits.shape    ,(self.batch_size, self.num_channels, self.image_size, self.image_size)				)

        # test greyscale images
        _UpperCAmelCase    :		Dict     	=					1
        _UpperCAmelCase    :		Optional[int]     	=					TFSwinForMaskedImageModeling(a_				)

        _UpperCAmelCase    :		Optional[int]     	=					floats_tensor([self.batch_size, 1, self.image_size, self.image_size]				)
        _UpperCAmelCase    :		List[Any]     	=					model(a_				)
        self.parent.assertEqual(result.logits.shape    ,(self.batch_size, 1, self.image_size, self.image_size)				)







 def _snake_case					(				self    ,a_    ,a_    ,a_				)						->  Dict:
        _UpperCAmelCase    :		List[str]     	=					self.type_sequence_label_size
        _UpperCAmelCase    :		int     	=					TFSwinForImageClassification(a_				)
        _UpperCAmelCase    :		Optional[Any]     	=					model(a_    ,labels=a_				)
        self.parent.assertEqual(result.logits.shape    ,(self.batch_size, self.type_sequence_label_size)				)

        # test greyscale images
        _UpperCAmelCase    :		str     	=					1
        _UpperCAmelCase    :		List[Any]     	=					TFSwinForImageClassification(a_				)
        _UpperCAmelCase    :		Tuple     	=					floats_tensor([self.batch_size, 1, self.image_size, self.image_size]				)
        _UpperCAmelCase    :		Union[str, Any]     	=					model(a_				)
        self.parent.assertEqual(result.logits.shape    ,(self.batch_size, self.type_sequence_label_size)				)







 def _snake_case					(				self				)						->  Optional[int]:
        _UpperCAmelCase    :		str     	=					self.prepare_config_and_inputs()
        _UpperCAmelCase	,_UpperCAmelCase	,_UpperCAmelCase    :		List[str]     	=					config_and_inputs
        _UpperCAmelCase    :		Dict     	=					{"""pixel_values""": pixel_values}
        return config, inputs_dict







@require_tf
class 				lowercase			(    _lowerCamelCase   ,   _lowerCamelCase   ,   unittest.TestCase							):


 """simple docstring"""


 UpperCAmelCase		      =    (
     (
         TFSwinModel,
         TFSwinForImageClassification,
         TFSwinForMaskedImageModeling,
     )
     if is_tf_available()
     else ()
 )
 UpperCAmelCase		      =    (
     {"""feature-extraction""": TFSwinModel, """image-classification""": TFSwinForImageClassification}
     if is_tf_available()
     else {}
 )

 UpperCAmelCase		      =    False
 UpperCAmelCase		      =    False
 UpperCAmelCase		      =    False
 UpperCAmelCase		      =    False







 def _snake_case					(				self				)						->  Optional[Any]:
        _UpperCAmelCase    :		List[Any]     	=					TFSwinModelTester(self				)
        _UpperCAmelCase    :		Dict     	=					ConfigTester(self    ,config_class=a_    ,embed_dim=37				)







 def _snake_case					(				self				)						->  Union[str, 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 _snake_case					(				self				)						->  List[Any]:
        return







 def _snake_case					(				self				)						->  List[Any]:
        _UpperCAmelCase    :		Optional[int]     	=					self.model_tester.prepare_config_and_inputs()
        self.model_tester.create_and_check_model(*a_				)







 def _snake_case					(				self				)						->  Any:
        _UpperCAmelCase    :		Dict     	=					self.model_tester.prepare_config_and_inputs()
        self.model_tester.create_and_check_for_masked_image_modeling(*a_				)







 def _snake_case					(				self				)						->  Dict:
        _UpperCAmelCase    :		Any     	=					self.model_tester.prepare_config_and_inputs()
        self.model_tester.create_and_check_for_image_classification(*a_				)







 @unittest.skip(reason="""Swin does not use inputs_embeds"""				)
 def _snake_case					(				self				)						->  Dict:
        pass







 def _snake_case					(				self				)						->  Dict:
        _UpperCAmelCase	,_UpperCAmelCase    :		int     	=					self.model_tester.prepare_config_and_inputs_for_common()

        for model_class in self.all_model_classes:
               _UpperCAmelCase    :		Optional[Any]     	=					model_class(a_				)
               self.assertIsInstance(model.get_input_embeddings()    ,tf.keras.layers.Layer				)
               _UpperCAmelCase    :		Any     	=					model.get_output_embeddings()
               self.assertTrue(x is None or isinstance(a_    ,tf.keras.layers.Dense				)				)







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

        for model_class in self.all_model_classes:
               _UpperCAmelCase    :		Optional[Any]     	=					model_class(a_				)
               _UpperCAmelCase    :		int     	=					inspect.signature(model.call				)
               # signature.parameters is an OrderedDict => so arg_names order is deterministic
               _UpperCAmelCase    :		Union[str, Any]     	=					[*signature.parameters.keys()]

               _UpperCAmelCase    :		Tuple     	=					["""pixel_values"""]
               self.assertListEqual(arg_names[:1]    ,a_				)







 def _snake_case					(				self				)						->  int:
        _UpperCAmelCase	,_UpperCAmelCase    :		str     	=					self.model_tester.prepare_config_and_inputs_for_common()
        _UpperCAmelCase    :		str     	=					True

        for model_class in self.all_model_classes:
               _UpperCAmelCase    :		Dict     	=					True
               _UpperCAmelCase    :		Dict     	=					False
               _UpperCAmelCase    :		Any     	=					True
               _UpperCAmelCase    :		int     	=					model_class(a_				)
               _UpperCAmelCase    :		Optional[Any]     	=					model(**self._prepare_for_class(a_    ,a_				)				)
               _UpperCAmelCase    :		List[str]     	=					outputs.attentions
               _UpperCAmelCase    :		int     	=					len(self.model_tester.depths				)
               self.assertEqual(len(a_				)    ,a_				)

               # check that output_attentions also work using config
               del inputs_dict["output_attentions"]
               _UpperCAmelCase    :		str     	=					True
               _UpperCAmelCase    :		Optional[int]     	=					config.window_size**2
               _UpperCAmelCase    :		Optional[int]     	=					model_class(a_				)
               _UpperCAmelCase    :		List[Any]     	=					model(**self._prepare_for_class(a_    ,a_				)				)
               _UpperCAmelCase    :		List[Any]     	=					outputs.attentions
               self.assertEqual(len(a_				)    ,a_				)

               self.assertListEqual(
                   list(attentions[0].shape[-3:]				)    ,[self.model_tester.num_heads[0], window_size_squared, window_size_squared]    ,)
               _UpperCAmelCase    :		List[Any]     	=					len(a_				)

               # Check attention is always last and order is fine
               _UpperCAmelCase    :		Any     	=					True
               _UpperCAmelCase    :		Any     	=					True
               _UpperCAmelCase    :		Union[str, Any]     	=					model_class(a_				)
               _UpperCAmelCase    :		str     	=					model(**self._prepare_for_class(a_    ,a_				)				)

               if hasattr(self.model_tester    ,"""num_hidden_states_types"""				):
                      _UpperCAmelCase    :		Tuple     	=					self.model_tester.num_hidden_states_types
               else:
                      # also another +1 for reshaped_hidden_states
                      _UpperCAmelCase    :		Dict     	=					2
               self.assertEqual(out_len + added_hidden_states    ,len(a_				)				)

               _UpperCAmelCase    :		int     	=					outputs.attentions

               self.assertEqual(len(a_				)    ,a_				)

               self.assertListEqual(
                   list(self_attentions[0].shape[-3:]				)    ,[self.model_tester.num_heads[0], window_size_squared, window_size_squared]    ,)







 def _snake_case					(				self    ,a_    ,a_    ,a_    ,a_				)						->  Union[str, Any]:
        _UpperCAmelCase    :		List[Any]     	=					model_class(a_				)
        _UpperCAmelCase    :		Dict     	=					model(**self._prepare_for_class(a_    ,a_				)				)
        _UpperCAmelCase    :		List[Any]     	=					outputs.hidden_states

        _UpperCAmelCase    :		List[str]     	=					getattr(
            self.model_tester    ,"""expected_num_hidden_layers"""    ,len(self.model_tester.depths				) + 1				)
        self.assertEqual(len(a_				)    ,a_				)

        # Swin has a different seq_length
        _UpperCAmelCase    :		Tuple     	=					to_atuple(config.patch_size				)

        _UpperCAmelCase    :		List[str]     	=					(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

        self.assertListEqual(
            list(hidden_states[0].shape[-2:]				)    ,[num_patches, self.model_tester.embed_dim]    ,)

        _UpperCAmelCase    :		Union[str, Any]     	=					outputs.reshaped_hidden_states
        self.assertEqual(len(a_				)    ,a_				)

        _UpperCAmelCase	,_UpperCAmelCase	,_UpperCAmelCase	,_UpperCAmelCase    :		Optional[int]     	=					reshaped_hidden_states[0].shape

        _UpperCAmelCase    :		List[Any]     	=					tf.reshape(reshaped_hidden_states[0]    ,(batch_size, num_channels, height * width)				)
        _UpperCAmelCase    :		Optional[int]     	=					tf.transpose(a_    ,(0, 2, 1)				)

        self.assertListEqual(
            list(reshaped_hidden_states.shape[-2:]				)    ,[num_patches, self.model_tester.embed_dim]    ,)







 def _snake_case					(				self				)						->  Dict:
        _UpperCAmelCase	,_UpperCAmelCase    :		List[Any]     	=					self.model_tester.prepare_config_and_inputs_for_common()

        _UpperCAmelCase    :		int     	=					to_atuple(self.model_tester.image_size				)

        for model_class in self.all_model_classes:
               _UpperCAmelCase    :		Tuple     	=					True
               self.check_hidden_states_output(a_    ,a_    ,a_    ,a_				)

               # check that output_hidden_states also work using config
               del inputs_dict["output_hidden_states"]
               _UpperCAmelCase    :		Any     	=					True

               self.check_hidden_states_output(a_    ,a_    ,a_    ,a_				)







 def _snake_case					(				self				)						->  Any:
        _UpperCAmelCase	,_UpperCAmelCase    :		str     	=					self.model_tester.prepare_config_and_inputs_for_common()
        _UpperCAmelCase    :		Union[str, Any]     	=					3

        _UpperCAmelCase    :		Optional[int]     	=					to_atuple(self.model_tester.image_size				)
        _UpperCAmelCase    :		Dict     	=					to_atuple(config.patch_size				)

        _UpperCAmelCase    :		Optional[int]     	=					image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
        _UpperCAmelCase    :		int     	=					image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

        for model_class in self.all_model_classes:
               _UpperCAmelCase    :		str     	=					True
               self.check_hidden_states_output(a_    ,a_    ,a_    ,(padded_height, padded_width)				)

               # check that output_hidden_states also work using config
               del inputs_dict["output_hidden_states"]
               _UpperCAmelCase    :		Any     	=					True
               self.check_hidden_states_output(a_    ,a_    ,a_    ,(padded_height, padded_width)				)







 @slow
 def _snake_case					(				self				)						->  Any:
        for model_name in TF_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
               _UpperCAmelCase    :		Any     	=					TFSwinModel.from_pretrained(a_				)
               self.assertIsNotNone(a_				)







@require_vision
@require_tf
class 				lowercase			(    unittest.TestCase							):


 """simple docstring"""


 @cached_property
 def _snake_case					(				self				)						->  Optional[Any]:
        return (
            AutoImageProcessor.from_pretrained("""microsoft/swin-tiny-patch4-window7-224"""				)
            if is_vision_available()
            else None
        )







 @slow
 def _snake_case					(				self				)						->  Any:
        _UpperCAmelCase    :		str     	=					TFSwinForImageClassification.from_pretrained("""microsoft/swin-tiny-patch4-window7-224"""				)
        _UpperCAmelCase    :		Optional[int]     	=					self.default_image_processor

        _UpperCAmelCase    :		Dict     	=					Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""				)
        _UpperCAmelCase    :		Tuple     	=					image_processor(images=a_    ,return_tensors="""tf"""				)

        # forward pass
        _UpperCAmelCase    :		Optional[Any]     	=					model(a_				)

        # verify the logits
        _UpperCAmelCase    :		Optional[int]     	=					tf.TensorShape((1, 1_000)				)
        self.assertEqual(outputs.logits.shape    ,a_				)
        _UpperCAmelCase    :		Any     	=					tf.constant([-0.0948, -0.6454, -0.0921]				)
        self.assertTrue(np.allclose(outputs.logits[0, :3]    ,a_    ,atol=1E-4				)				)





'''simple docstring'''

def        SCREAMING_SNAKE_CASE_  (	snake_case_				:	int   ,     snake_case_				:	list[tuple[int, int, int]]							)       ->	list[tuple[int, int, int]]:
 SCREAMING_SNAKE_CASE  :  List[Any]								=		sorted(snake_case_   ,     key=lambda snake_case_							: edge[2]							)

 SCREAMING_SNAKE_CASE  :  str								=		list(range(snake_case_							)							)

 def find_parent(snake_case_				:	Union[str, Any]							):
  if i != parent[i]:
   SCREAMING_SNAKE_CASE  :  int								=		find_parent(parent[i]							)
  return parent[i]

 SCREAMING_SNAKE_CASE  :  Union[str, Any]								=		0
 SCREAMING_SNAKE_CASE  :  Any								=		[]

 for edge in edges:
  SCREAMING_SNAKE_CASE  :  Dict								=		find_parent(edge[0]							)
  SCREAMING_SNAKE_CASE  :  Optional[int]								=		find_parent(edge[1]							)
  if parent_a != parent_b:
   minimum_spanning_tree_cost += edge[2]
   minimum_spanning_tree.append(snake_case_							)
   SCREAMING_SNAKE_CASE  :  Tuple								=		parent_b

 return minimum_spanning_tree


if __name__ == "__main__":  # pragma: no cover
   __UpperCAmelCase						,						__UpperCAmelCase												=   list(map(int, input().strip().split()))
   __UpperCAmelCase												=   []

   for _ in range(num_edges):
      __UpperCAmelCase						,						__UpperCAmelCase						,						__UpperCAmelCase												=   (int(x) for x in input().strip().split())
      edges.append((nodea, nodea, cost))

   kruskal(num_nodes, edges)


