'''simple docstring'''
import inspect
import unittest

from transformers import YolosConfig
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
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
  import torch
  from torch import nn

  from transformers import YolosForObjectDetection, YolosModel
  from transformers.models.yolos.modeling_yolos import YOLOS_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
  from PIL import Image

  from transformers import AutoImageProcessor






class 			__lowercase		:







     """simple docstring"""






     def __init__(		self     ,			_lowerCamelCase     ,			_lowerCamelCase=1_3     ,			_lowerCamelCase=[3_0, 3_0]     ,			_lowerCamelCase=2     ,			_lowerCamelCase=3     ,			_lowerCamelCase=True     ,			_lowerCamelCase=True     ,			_lowerCamelCase=3_2     ,			_lowerCamelCase=5     ,			_lowerCamelCase=4     ,			_lowerCamelCase=3_7     ,			_lowerCamelCase="gelu"     ,			_lowerCamelCase=0.1     ,			_lowerCamelCase=0.1     ,			_lowerCamelCase=1_0     ,			_lowerCamelCase=0.0_2     ,			_lowerCamelCase=3     ,			_lowerCamelCase=None     ,			_lowerCamelCase=8     ,			_lowerCamelCase=1_0     ,			):
         __UpperCamelCase	:	int		    =  parent
         __UpperCamelCase	:	Any		    =  batch_size
         __UpperCamelCase	:	int		    =  image_size
         __UpperCamelCase	:	Optional[int]		    =  patch_size
         __UpperCamelCase	:	Any		    =  num_channels
         __UpperCamelCase	:	Union[str, Any]		    =  is_training
         __UpperCamelCase	:	Union[str, Any]		    =  use_labels
         __UpperCamelCase	:	Union[str, Any]		    =  hidden_size
         __UpperCamelCase	:	Dict		    =  num_hidden_layers
         __UpperCamelCase	:	int		    =  num_attention_heads
         __UpperCamelCase	:	Optional[Any]		    =  intermediate_size
         __UpperCamelCase	:	Tuple		    =  hidden_act
         __UpperCamelCase	:	Union[str, Any]		    =  hidden_dropout_prob
         __UpperCamelCase	:	Optional[Any]		    =  attention_probs_dropout_prob
         __UpperCamelCase	:	List[str]		    =  type_sequence_label_size
         __UpperCamelCase	:	str		    =  initializer_range
         __UpperCamelCase	:	int		    =  num_labels
         __UpperCamelCase	:	str		    =  scope
         __UpperCamelCase	:	Tuple		    =  n_targets
         __UpperCamelCase	:	Optional[Any]		    =  num_detection_tokens
         # we set the expected sequence length (which is used in several tests)
         # expected sequence length = num_patches + 1 (we add 1 for the [CLS] token) + num_detection_tokens
         __UpperCamelCase	:	Dict		    =  (image_size[1] // patch_size) * (image_size[0] // patch_size)
         __UpperCamelCase	:	Any		    =  num_patches + 1 + self.num_detection_tokens







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	List[str]		    =  floats_tensor([self.batch_size, self.num_channels, self.image_size[0], self.image_size[1]]    )

         __UpperCamelCase	:	str		    =  None
         if self.use_labels:
             # labels is a list of Dict (each Dict being the labels for a given example in the batch)
             __UpperCamelCase	:	Optional[int]		    =  []
             for i in range(self.batch_size    ):
                 __UpperCamelCase	:	int		    =  {}
                 __UpperCamelCase	:	Any		    =  torch.randint(
                     high=self.num_labels     ,			size=(self.n_targets,)     ,			device=_lowerCamelCase    )
                 __UpperCamelCase	:	List[str]		    =  torch.rand(self.n_targets     ,			4     ,			device=_lowerCamelCase    )
                 labels.append(_lowerCamelCase    )

         __UpperCamelCase	:	int		    =  self.get_config()

         return config, pixel_values, labels







     def lowerCAmelCase     (		self    ):
         return YolosConfig(
             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=_lowerCamelCase     ,			initializer_range=self.initializer_range     ,			num_detection_tokens=self.num_detection_tokens     ,			num_labels=self.num_labels     ,			)







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	int		    =  YolosModel(config=_lowerCamelCase    )
         model.to(_lowerCamelCase    )
         model.eval()
         __UpperCamelCase	:	Tuple		    =  model(_lowerCamelCase    )
         self.parent.assertEqual(
             result.last_hidden_state.shape     ,			(self.batch_size, self.expected_seq_len, self.hidden_size)    )







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         __UpperCamelCase	:	int		    =  YolosForObjectDetection(_lowerCamelCase    )
         model.to(_lowerCamelCase    )
         model.eval()

         __UpperCamelCase	:	Optional[Any]		    =  model(pixel_values=_lowerCamelCase    )
         __UpperCamelCase	:	List[Any]		    =  model(_lowerCamelCase    )

         self.parent.assertEqual(result.logits.shape     ,			(self.batch_size, self.num_detection_tokens, self.num_labels + 1)    )
         self.parent.assertEqual(result.pred_boxes.shape     ,			(self.batch_size, self.num_detection_tokens, 4)    )

         __UpperCamelCase	:	Optional[Any]		    =  model(pixel_values=_lowerCamelCase     ,			labels=_lowerCamelCase    )

         self.parent.assertEqual(result.loss.shape     ,			()    )
         self.parent.assertEqual(result.logits.shape     ,			(self.batch_size, self.num_detection_tokens, self.num_labels + 1)    )
         self.parent.assertEqual(result.pred_boxes.shape     ,			(self.batch_size, self.num_detection_tokens, 4)    )







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	Tuple		    =  self.prepare_config_and_inputs()
         __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	str		    =  config_and_inputs
         __UpperCamelCase	:	Optional[Any]		    =  {'pixel_values': pixel_values}
         return config, inputs_dict






@require_torch
class 			__lowercase		(						_lowerCamelCase			,							_lowerCamelCase			,							unittest.TestCase						):







     """simple docstring"""






     SCREAMING_SNAKE_CASE__		   =						(YolosModel, YolosForObjectDetection) if is_torch_available() else ()
     SCREAMING_SNAKE_CASE__		   =						(
         {'''feature-extraction''': YolosModel, '''object-detection''': YolosForObjectDetection} if is_torch_available() else {}
     )

     SCREAMING_SNAKE_CASE__		   =						False
     SCREAMING_SNAKE_CASE__		   =						False
     SCREAMING_SNAKE_CASE__		   =						False
     SCREAMING_SNAKE_CASE__		   =						False







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase=False    ):
         __UpperCamelCase	:	Union[str, Any]		    =  super()._prepare_for_class(_lowerCamelCase     ,			_lowerCamelCase     ,			return_labels=_lowerCamelCase    )

         if return_labels:
             if model_class.__name__ == "YolosForObjectDetection":
                 __UpperCamelCase	:	List[str]		    =  []
                 for i in range(self.model_tester.batch_size    ):
                     __UpperCamelCase	:	List[Any]		    =  {}
                     __UpperCamelCase	:	Any		    =  torch.ones(
                         size=(self.model_tester.n_targets,)     ,			device=_lowerCamelCase     ,			dtype=torch.long    )
                     __UpperCamelCase	:	int		    =  torch.ones(
                         self.model_tester.n_targets     ,			4     ,			device=_lowerCamelCase     ,			dtype=torch.float    )
                     labels.append(_lowerCamelCase    )
                 __UpperCamelCase	:	List[str]		    =  labels

         return inputs_dict







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	Union[str, Any]		    =  YolosModelTester(self    )
         __UpperCamelCase	:	Any		    =  ConfigTester(self     ,			config_class=_lowerCamelCase     ,			has_text_modality=_lowerCamelCase     ,			hidden_size=3_7    )







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







     def lowerCAmelCase     (		self    ):
         # YOLOS does not use inputs_embeds
         pass







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase    ,					__UpperCamelCase	:	Any		    =  self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
             __UpperCamelCase	:	int		    =  model_class(_lowerCamelCase    )
             self.assertIsInstance(model.get_input_embeddings()     ,			(nn.Module)    )
             __UpperCamelCase	:	Union[str, Any]		    =  model.get_output_embeddings()
             self.assertTrue(x is None or isinstance(_lowerCamelCase     ,			nn.Linear    )    )







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase    ,					__UpperCamelCase	:	Optional[Any]		    =  self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
             __UpperCamelCase	:	List[str]		    =  model_class(_lowerCamelCase    )
             __UpperCamelCase	:	Optional[int]		    =  inspect.signature(model.forward    )
             # signature.parameters is an OrderedDict => so arg_names order is deterministic
             __UpperCamelCase	:	str		    =  [*signature.parameters.keys()]

             __UpperCamelCase	:	Tuple		    =  ['pixel_values']
             self.assertListEqual(arg_names[:1]     ,			_lowerCamelCase    )







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	List[str]		    =  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_model(*_lowerCamelCase    )







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase    ,					__UpperCamelCase	:	Tuple		    =  self.model_tester.prepare_config_and_inputs_for_common()
         __UpperCamelCase	:	Optional[int]		    =  True

         # in YOLOS, the seq_len is different
         __UpperCamelCase	:	str		    =  self.model_tester.expected_seq_len
         for model_class in self.all_model_classes:
             __UpperCamelCase	:	Union[str, Any]		    =  True
             __UpperCamelCase	:	int		    =  False
             __UpperCamelCase	:	str		    =  True
             __UpperCamelCase	:	int		    =  model_class(_lowerCamelCase    )
             model.to(_lowerCamelCase    )
             model.eval()
             with torch.no_grad():
                 __UpperCamelCase	:	Tuple		    =  model(**self._prepare_for_class(_lowerCamelCase     ,			_lowerCamelCase    )    )
             __UpperCamelCase	:	Optional[Any]		    =  outputs.attentions
             self.assertEqual(len(_lowerCamelCase    )     ,			self.model_tester.num_hidden_layers    )

             # check that output_attentions also work using config
             del inputs_dict["output_attentions"]
             __UpperCamelCase	:	int		    =  True
             __UpperCamelCase	:	Any		    =  model_class(_lowerCamelCase    )
             model.to(_lowerCamelCase    )
             model.eval()
             with torch.no_grad():
                 __UpperCamelCase	:	Tuple		    =  model(**self._prepare_for_class(_lowerCamelCase     ,			_lowerCamelCase    )    )
             __UpperCamelCase	:	Dict		    =  outputs.attentions
             self.assertEqual(len(_lowerCamelCase    )     ,			self.model_tester.num_hidden_layers    )

             self.assertListEqual(
                 list(attentions[0].shape[-3:]    )     ,			[self.model_tester.num_attention_heads, seq_len, seq_len]     ,			)
             __UpperCamelCase	:	str		    =  len(_lowerCamelCase    )

             # Check attention is always last and order is fine
             __UpperCamelCase	:	Tuple		    =  True
             __UpperCamelCase	:	Union[str, Any]		    =  True
             __UpperCamelCase	:	Tuple		    =  model_class(_lowerCamelCase    )
             model.to(_lowerCamelCase    )
             model.eval()
             with torch.no_grad():
                 __UpperCamelCase	:	List[str]		    =  model(**self._prepare_for_class(_lowerCamelCase     ,			_lowerCamelCase    )    )

             __UpperCamelCase	:	int		    =  1
             self.assertEqual(out_len + added_hidden_states     ,			len(_lowerCamelCase    )    )

             __UpperCamelCase	:	Any		    =  outputs.attentions

             self.assertEqual(len(_lowerCamelCase    )     ,			self.model_tester.num_hidden_layers    )
             self.assertListEqual(
                 list(self_attentions[0].shape[-3:]    )     ,			[self.model_tester.num_attention_heads, seq_len, seq_len]     ,			)







     def lowerCAmelCase     (		self    ):
         def check_hidden_states_output(_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
             __UpperCamelCase	:	Any		    =  model_class(_lowerCamelCase    )
             model.to(_lowerCamelCase    )
             model.eval()

             with torch.no_grad():
                 __UpperCamelCase	:	Optional[Any]		    =  model(**self._prepare_for_class(_lowerCamelCase     ,			_lowerCamelCase    )    )

             __UpperCamelCase	:	Union[str, Any]		    =  outputs.hidden_states

             __UpperCamelCase	:	Optional[Any]		    =  getattr(
                 self.model_tester     ,			'expected_num_hidden_layers'     ,			self.model_tester.num_hidden_layers + 1    )
             self.assertEqual(len(_lowerCamelCase    )     ,			_lowerCamelCase    )

             # YOLOS has a different seq_length
             __UpperCamelCase	:	Any		    =  self.model_tester.expected_seq_len

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

         __UpperCamelCase    ,					__UpperCamelCase	:	Optional[int]		    =  self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
             __UpperCamelCase	:	List[str]		    =  True
             check_hidden_states_output(_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    )

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

             check_hidden_states_output(_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    )







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	List[str]		    =  self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_object_detection(*_lowerCamelCase    )







     @slow
     def lowerCAmelCase     (		self    ):
         for model_name in YOLOS_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
             __UpperCamelCase	:	Tuple		    =  YolosModel.from_pretrained(_lowerCamelCase    )
             self.assertIsNotNone(_lowerCamelCase    )







def  _UpperCamelCase (     ):




    """simple docstring"""



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






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







     """simple docstring"""






     @cached_property
     def lowerCAmelCase     (		self    ):
         return AutoImageProcessor.from_pretrained('hustvl/yolos-small'    ) if is_vision_available() else None







     @slow
     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	List[Any]		    =  YolosForObjectDetection.from_pretrained('hustvl/yolos-small'    ).to(_lowerCamelCase    )

         __UpperCamelCase	:	int		    =  self.default_image_processor
         __UpperCamelCase	:	int		    =  prepare_img()
         __UpperCamelCase	:	Any		    =  image_processor(images=_lowerCamelCase     ,			return_tensors='pt'    ).to(_lowerCamelCase    )

         # forward pass
         with torch.no_grad():
             __UpperCamelCase	:	Union[str, Any]		    =  model(inputs.pixel_values    )

         # verify outputs
         __UpperCamelCase	:	Any		    =  torch.Size((1, 1_0_0, 9_2)    )
         self.assertEqual(outputs.logits.shape     ,			_lowerCamelCase    )

         __UpperCamelCase	:	str		    =  torch.tensor(
             [[-2_4.0_2_4_8, -1_0.3_0_2_4, -1_4.8_2_9_0], [-4_2.0_3_9_2, -1_6.8_2_0_0, -2_7.4_3_3_4], [-2_7.2_7_4_3, -1_1.8_1_5_4, -1_8.7_1_4_8]]     ,			device=_lowerCamelCase     ,			)
         __UpperCamelCase	:	int		    =  torch.tensor(
             [[0.2_5_5_9, 0.5_4_5_5, 0.4_7_0_6], [0.2_9_8_9, 0.7_2_7_9, 0.1_8_7_5], [0.7_7_3_2, 0.4_0_1_7, 0.4_4_6_2]]     ,			device=_lowerCamelCase    )
         self.assertTrue(torch.allclose(outputs.logits[0, :3, :3]     ,			_lowerCamelCase     ,			atol=1E-4    )    )
         self.assertTrue(torch.allclose(outputs.pred_boxes[0, :3, :3]     ,			_lowerCamelCase     ,			atol=1E-4    )    )

         # verify postprocessing
         __UpperCamelCase	:	Dict		    =  image_processor.post_process_object_detection(
             _lowerCamelCase     ,			threshold=0.3     ,			target_sizes=[image.size[::-1]]    )[0]
         __UpperCamelCase	:	List[str]		    =  torch.tensor([0.9_9_9_4, 0.9_7_9_0, 0.9_9_6_4, 0.9_9_7_2, 0.9_8_6_1]    ).to(_lowerCamelCase    )
         __UpperCamelCase	:	Dict		    =  [7_5, 7_5, 1_7, 6_3, 1_7]
         __UpperCamelCase	:	List[Any]		    =  torch.tensor([3_3_5.0_6_0_9, 7_9.3_8_4_8, 3_7_5.4_2_1_6, 1_8_7.2_4_9_5]    ).to(_lowerCamelCase    )

         self.assertEqual(len(results['scores']    )     ,			5    )
         self.assertTrue(torch.allclose(results['scores']     ,			_lowerCamelCase     ,			atol=1E-4    )    )
         self.assertSequenceEqual(results['labels'].tolist()     ,			_lowerCamelCase    )
         self.assertTrue(torch.allclose(results['boxes'][0, :]     ,			_lowerCamelCase    )    )




'''simple docstring'''
class 			__lowercase		:







     """simple docstring"""






     def __init__(		self    ):
         __UpperCamelCase	:	Any		    =  0
         __UpperCamelCase	:	Any		    =  0
         __UpperCamelCase	:	Any		    =  {}







     def lowerCAmelCase     (		self     ,			_lowerCamelCase    ):
         if vertex not in self.adjacency:
             __UpperCamelCase	:	Tuple		    =  {}
             self.num_vertices += 1







     def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
         self.add_vertex(_lowerCamelCase    )
         self.add_vertex(_lowerCamelCase    )

         if head == tail:
             return

         __UpperCamelCase	:	List[Any]		    =  weight
         __UpperCamelCase	:	Optional[int]		    =  weight







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	List[str]		    =  self.get_edges()
         for edge in edges:
             __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	Optional[int]		    =  edge
             edges.remove((tail, head, weight)    )
         for i in range(len(_lowerCamelCase    )    ):
             __UpperCamelCase	:	Union[str, Any]		    =  list(edges[i]    )

         edges.sort(key=lambda _lowerCamelCase    : e[2]    )
         for i in range(len(_lowerCamelCase    ) - 1    ):
             if edges[i][2] >= edges[i + 1][2]:
                 __UpperCamelCase	:	Optional[int]		    =  edges[i][2] + 1
         for edge in edges:
             __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	Optional[int]		    =  edge
             __UpperCamelCase	:	Tuple		    =  weight
             __UpperCamelCase	:	Optional[Any]		    =  weight







     def __str__(		self    ):
         __UpperCamelCase	:	Optional[Any]		    =  ''
         for tail in self.adjacency:
             for head in self.adjacency[tail]:
                 __UpperCamelCase	:	Tuple		    =  self.adjacency[head][tail]
                 string += f"""{head} -> {tail} == {weight}\n"""
         return string.rstrip('\n'    )







     def lowerCAmelCase     (		self    ):
         __UpperCamelCase	:	Any		    =  []
         for tail in self.adjacency:
             for head in self.adjacency[tail]:
                 output.append((tail, head, self.adjacency[head][tail])    )
         return output







     def lowerCAmelCase     (		self    ):
         return self.adjacency.keys()







     @staticmethod
     def lowerCAmelCase     (		_lowerCamelCase=None     ,			_lowerCamelCase=None    ):
         __UpperCamelCase	:	Tuple		    =  Graph()
         if vertices is None:
             __UpperCamelCase	:	List[Any]		    =  []
         if edges is None:
             __UpperCamelCase	:	Optional[int]		    =  []
         for vertex in vertices:
             g.add_vertex(_lowerCamelCase    )
         for edge in edges:
             g.add_edge(*_lowerCamelCase    )
         return g






     class 			__lowercase		:







          """simple docstring"""






          def __init__(		self    ):
              __UpperCamelCase	:	Union[str, Any]		    =  {}
              __UpperCamelCase	:	int		    =  {}







          def __len__(		self    ):
              return len(self.parent    )







          def lowerCAmelCase     (		self     ,			_lowerCamelCase    ):
              if item in self.parent:
                  return self.find(_lowerCamelCase    )

              __UpperCamelCase	:	Optional[Any]		    =  item
              __UpperCamelCase	:	List[str]		    =  0
              return item







          def lowerCAmelCase     (		self     ,			_lowerCamelCase    ):
              if item not in self.parent:
                  return self.make_set(_lowerCamelCase    )
              if item != self.parent[item]:
                  __UpperCamelCase	:	int		    =  self.find(self.parent[item]    )
              return self.parent[item]







          def lowerCAmelCase     (		self     ,			_lowerCamelCase     ,			_lowerCamelCase    ):
              __UpperCamelCase	:	Tuple		    =  self.find(_lowerCamelCase    )
              __UpperCamelCase	:	Any		    =  self.find(_lowerCamelCase    )

              if roota == roota:
                  return roota

              if self.rank[roota] > self.rank[roota]:
                  __UpperCamelCase	:	Dict		    =  roota
                  return roota

              if self.rank[roota] < self.rank[roota]:
                  __UpperCamelCase	:	Optional[Any]		    =  roota
                  return roota

              if self.rank[roota] == self.rank[roota]:
                  self.rank[roota] += 1
                  __UpperCamelCase	:	Dict		    =  roota
                  return roota
              return None







     @staticmethod
     def lowerCAmelCase     (		_lowerCamelCase    ):
         __UpperCamelCase	:	int		    =  graph.num_vertices

         __UpperCamelCase	:	str		    =  Graph.UnionFind()
         __UpperCamelCase	:	Tuple		    =  []
         while num_components > 1:
             __UpperCamelCase	:	Dict		    =  {}
             for vertex in graph.get_vertices():
                 __UpperCamelCase	:	str		    =  -1

             __UpperCamelCase	:	int		    =  graph.get_edges()
             for edge in edges:
                 __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	List[str]		    =  edge
                 edges.remove((tail, head, weight)    )
             for edge in edges:
                 __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	Dict		    =  edge
                 __UpperCamelCase	:	List[Any]		    =  union_find.find(_lowerCamelCase    )
                 __UpperCamelCase	:	str		    =  union_find.find(_lowerCamelCase    )
                 if seta != seta:
                     if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                         __UpperCamelCase	:	str		    =  [head, tail, weight]

                     if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
                         __UpperCamelCase	:	str		    =  [head, tail, weight]
             for vertex in cheap_edge:
                 if cheap_edge[vertex] != -1:
                     __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	List[str]		    =  cheap_edge[vertex]
                     if union_find.find(_lowerCamelCase    ) != union_find.find(_lowerCamelCase    ):
                         union_find.union(_lowerCamelCase     ,			_lowerCamelCase    )
                         mst_edges.append(cheap_edge[vertex]    )
                         __UpperCamelCase	:	int		    =  num_components - 1
         __UpperCamelCase	:	Union[str, Any]		    =  Graph.build(edges=_lowerCamelCase    )
         return mst



