



"""simple docstring"""

import inspect
import unittest

from datasets import load_dataset
from packaging import version

from transformers import BeitConfig
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_torch_multi_gpu, 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, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
     import torch
     from torch import nn

     from transformers import (
         MODEL_MAPPING,
         BeitForImageClassification,
         BeitForMaskedImageModeling,
         BeitForSemanticSegmentation,
         BeitModel,
     )
     from transformers.models.beit.modeling_beit import BEIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
     import PIL
     from PIL import Image

     from transformers import BeitImageProcessor




class        _UpperCAmelCase       :

 def __init__(     self		:       Optional[int]  ,     lowercase_		:       Tuple  ,     lowercase_		:       List[Any]=100  ,     lowercase_		:       str=13  ,     lowercase_		:       List[str]=30  ,     lowercase_		:       str=2  ,     lowercase_		:       int=3  ,     lowercase_		:       Tuple=True  ,     lowercase_		:       List[str]=True  ,     lowercase_		:       Union[str, Any]=32  ,     lowercase_		:       Dict=4  ,     lowercase_		:       Optional[Any]=4  ,     lowercase_		:       str=37  ,     lowercase_		:       Tuple="gelu"  ,     lowercase_		:       List[Any]=0.1  ,     lowercase_		:       Optional[int]=0.1  ,     lowercase_		:       List[Any]=10  ,     lowercase_		:       Any=0.02  ,     lowercase_		:       Any=3  ,     lowercase_		:       Dict=None  ,     lowercase_		:       List[Any]=[0, 1, 2, 3]  ,     ):
     snake_case_ :     Tuple				=	parent
     snake_case_ :     Dict				=	100
     snake_case_ :     List[Any]				=	batch_size
     snake_case_ :     Dict				=	image_size
     snake_case_ :     Union[str, Any]				=	patch_size
     snake_case_ :     Any				=	num_channels
     snake_case_ :     Optional[int]				=	is_training
     snake_case_ :     Optional[int]				=	use_labels
     snake_case_ :     List[str]				=	hidden_size
     snake_case_ :     Dict				=	num_hidden_layers
     snake_case_ :     Any				=	num_attention_heads
     snake_case_ :     int				=	intermediate_size
     snake_case_ :     Dict				=	hidden_act
     snake_case_ :     str				=	hidden_dropout_prob
     snake_case_ :     int				=	attention_probs_dropout_prob
     snake_case_ :     Optional[Any]				=	type_sequence_label_size
     snake_case_ :     Optional[int]				=	initializer_range
     snake_case_ :     Optional[int]				=	scope
     snake_case_ :     Tuple				=	out_indices
     snake_case_ :     Tuple				=	num_labels

     # in BeiT, the seq length equals the number of patches + 1 (we add 1 for the [CLS] token)
     snake_case_ :     Optional[int]				=	(image_size // patch_size) ** 2
     snake_case_ :     Optional[Any]				=	num_patches + 1

 def 						_snake_case					(     self		:       Any				):
     snake_case_ :     Tuple				=	floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]				)

     snake_case_ :     Dict				=	None
     snake_case_ :     int				=	None
     if self.use_labels:
         snake_case_ :     Optional[int]				=	ids_tensor([self.batch_size]  ,     self.type_sequence_label_size				)
         snake_case_ :     List[Any]				=	ids_tensor([self.batch_size, self.image_size, self.image_size]  ,     self.num_labels				)

     snake_case_ :     Union[str, Any]				=	self.get_config()

     return config, pixel_values, labels, pixel_labels

 def 						_snake_case					(     self		:       Optional[int]				):
     return BeitConfig(
         vocab_size=self.vocab_size  ,     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=lowercase_  ,     initializer_range=self.initializer_range  ,     out_indices=self.out_indices  ,     )

 def 						_snake_case					(     self		:       int  ,     lowercase_		:       int  ,     lowercase_		:       Any  ,     lowercase_		:       int  ,     lowercase_		:       Dict				):
     snake_case_ :     List[Any]				=	BeitModel(config=lowercase_				)
     model.to(lowercase_				)
     model.eval()
     snake_case_ :     Optional[Any]				=	model(lowercase_				)
     self.parent.assertEqual(result.last_hidden_state.shape  ,     (self.batch_size, self.seq_length, self.hidden_size)				)

 def 						_snake_case					(     self		:       Any  ,     lowercase_		:       Any  ,     lowercase_		:       Tuple  ,     lowercase_		:       Union[str, Any]  ,     lowercase_		:       Any				):
     snake_case_ :     Optional[Any]				=	BeitForMaskedImageModeling(config=lowercase_				)
     model.to(lowercase_				)
     model.eval()
     snake_case_ :     List[Any]				=	model(lowercase_				)
     self.parent.assertEqual(result.logits.shape  ,     (self.batch_size, self.seq_length - 1, self.vocab_size)				)

 def 						_snake_case					(     self		:       List[str]  ,     lowercase_		:       Optional[int]  ,     lowercase_		:       List[Any]  ,     lowercase_		:       List[Any]  ,     lowercase_		:       Tuple				):
     snake_case_ :     str				=	self.type_sequence_label_size
     snake_case_ :     Union[str, Any]				=	BeitForImageClassification(lowercase_				)
     model.to(lowercase_				)
     model.eval()
     snake_case_ :     Union[str, Any]				=	model(lowercase_  ,     labels=lowercase_				)
     self.parent.assertEqual(result.logits.shape  ,     (self.batch_size, self.type_sequence_label_size)				)

     # test greyscale images
     snake_case_ :     Optional[Any]				=	1
     snake_case_ :     Optional[int]				=	BeitForImageClassification(lowercase_				)
     model.to(lowercase_				)
     model.eval()

     snake_case_ :     str				=	floats_tensor([self.batch_size, 1, self.image_size, self.image_size]				)
     snake_case_ :     Tuple				=	model(lowercase_  ,     labels=lowercase_				)
     self.parent.assertEqual(result.logits.shape  ,     (self.batch_size, self.type_sequence_label_size)				)

 def 						_snake_case					(     self		:       Optional[Any]  ,     lowercase_		:       Tuple  ,     lowercase_		:       Optional[int]  ,     lowercase_		:       int  ,     lowercase_		:       Union[str, Any]				):
     snake_case_ :     Any				=	self.num_labels
     snake_case_ :     List[Any]				=	BeitForSemanticSegmentation(lowercase_				)
     model.to(lowercase_				)
     model.eval()
     snake_case_ :     List[Any]				=	model(lowercase_				)
     self.parent.assertEqual(
         result.logits.shape  ,     (self.batch_size, self.num_labels, self.image_size * 2, self.image_size * 2)				)
     snake_case_ :     Dict				=	model(lowercase_  ,     labels=lowercase_				)
     self.parent.assertEqual(
         result.logits.shape  ,     (self.batch_size, self.num_labels, self.image_size * 2, self.image_size * 2)				)






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





@require_torch
class        _UpperCAmelCase       (			UpperCAmelCase__    ,     UpperCAmelCase__    ,     unittest.TestCase):
 _lowerCAmelCase   :			Tuple							=		(
     (BeitModel, BeitForImageClassification, BeitForMaskedImageModeling, BeitForSemanticSegmentation)
     if is_torch_available()
     else ()
 )
 _lowerCAmelCase   :			List[str]							=		(
     {
         "feature-extraction": BeitModel,
         "image-classification": BeitForImageClassification,
         "image-segmentation": BeitForSemanticSegmentation,
     }
     if is_torch_available()
     else {}
 )

 _lowerCAmelCase   :			List[Any]							=		False
 _lowerCAmelCase   :			Optional[int]							=		False
 _lowerCAmelCase   :			List[Any]							=		False

 def 						_snake_case					(     self		:       List[Any]				):
     snake_case_ :     Dict				=	BeitModelTester(self				)
     snake_case_ :     List[str]				=	ConfigTester(self  ,     config_class=lowercase_  ,     has_text_modality=lowercase_  ,     hidden_size=37				)

 def 						_snake_case					(     self		:       str				):
     self.config_tester.run_common_tests()

 @unittest.skip(reason='''BEiT does not use inputs_embeds'''				)
 def 						_snake_case					(     self		:       Any				):
     pass

 @require_torch_multi_gpu
 @unittest.skip(reason='''BEiT has some layers using `add_module` which doesn\'t work well with `nn.DataParallel`'''				)
 def 						_snake_case					(     self		:       Union[str, Any]				):
     pass

 def 						_snake_case					(     self		:       Any				):
     snake_case_ :     Union[str, Any]				=	self.model_tester.prepare_config_and_inputs_for_common()

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

 def 						_snake_case					(     self		:       str				):
     snake_case_ :     Union[str, Any]				=	self.model_tester.prepare_config_and_inputs_for_common()

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

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

 def 						_snake_case					(     self		:       Dict				):
     snake_case_ :     Tuple				=	self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_model(*lowercase_				)

 def 						_snake_case					(     self		:       List[Any]				):
     snake_case_ :     Optional[Any]				=	self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_masked_lm(*lowercase_				)

 def 						_snake_case					(     self		:       Dict				):
     snake_case_ :     List[Any]				=	self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_image_classification(*lowercase_				)

 def 						_snake_case					(     self		:       Union[str, Any]				):
     snake_case_ :     List[Any]				=	self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_semantic_segmentation(*lowercase_				)

 def 						_snake_case					(     self		:       str				):
     if not self.model_tester.is_training:
         return

     snake_case_ :     int				=	self.model_tester.prepare_config_and_inputs_for_common()
     snake_case_ :     Optional[Any]				=	True

     for model_class in self.all_model_classes:
         # we don't test BeitForMaskedImageModeling
         if model_class in [*get_values(lowercase_				), BeitForMaskedImageModeling]:
             continue

         snake_case_ :     Tuple				=	model_class(lowercase_				)
         model.to(lowercase_				)
         model.train()
         snake_case_ :     Optional[int]				=	self._prepare_for_class(lowercase_  ,     lowercase_  ,     return_labels=lowercase_				)
         snake_case_ :     List[Any]				=	model(**lowercase_				).loss
         loss.backward()

 def 						_snake_case					(     self		:       int				):
     snake_case_ :     Optional[int]				=	self.model_tester.prepare_config_and_inputs_for_common()
     if not self.model_tester.is_training:
         return

     snake_case_ :     List[str]				=	False
     snake_case_ :     int				=	True

     for model_class in self.all_model_classes:
         # we don't test BeitForMaskedImageModeling
         if (
             model_class in [*get_values(lowercase_				), BeitForMaskedImageModeling]
             or not model_class.supports_gradient_checkpointing
         ):
             continue

         snake_case_ :     Any				=	model_class(lowercase_				)
         model.gradient_checkpointing_enable()
         model.to(lowercase_				)
         model.train()
         snake_case_ :     Tuple				=	self._prepare_for_class(lowercase_  ,     lowercase_  ,     return_labels=lowercase_				)
         snake_case_ :     Dict				=	model(**lowercase_				).loss
         loss.backward()

 def 						_snake_case					(     self		:       List[str]				):
     snake_case_ :     Any				=	self.model_tester.prepare_config_and_inputs_for_common()

     snake_case_ :     Union[str, Any]				=	_config_zero_init(lowercase_				)
     for model_class in self.all_model_classes:
         snake_case_ :     Dict				=	model_class(config=lowercase_				)
         for name, param in model.named_parameters():
             # we skip lambda parameters as these require special initial values
             # determined by config.layer_scale_init_value
             if "lambda" in name:
                 continue
             if param.requires_grad:
                 self.assertIn(
                     ((param.data.mean() * 1E9).round() / 1E9).item()  ,     [0.0, 1.0]  ,     msg=f"Parameter {name} of model {model_class} seems not properly initialized"  ,     )






 @slow
 def 						_snake_case					(     self		:       str				):
     for model_name in BEIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
         snake_case_ :     Union[str, Any]				=	BeitModel.from_pretrained(lowercase_				)
         self.assertIsNotNone(lowercase_				)





def __lowercase			(							):
    snake_case_ :     List[Any]				=	Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''    )
    return image






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

 @cached_property
 def 						_snake_case					(     self		:       Dict				):
     return BeitImageProcessor.from_pretrained('''microsoft/beit-base-patch16-224'''				) if is_vision_available() else None

 @slow
 def 						_snake_case					(     self		:       Union[str, Any]				):
     snake_case_ :     Union[str, Any]				=	BeitForMaskedImageModeling.from_pretrained('''microsoft/beit-base-patch16-224-pt22k'''				).to(lowercase_				)

     snake_case_ :     Tuple				=	self.default_image_processor
     snake_case_ :     Union[str, Any]				=	prepare_img()
     snake_case_ :     Tuple				=	image_processor(images=lowercase_  ,     return_tensors='''pt'''				).pixel_values.to(lowercase_				)

     # prepare bool_masked_pos
     snake_case_ :     int				=	torch.ones((1, 196)  ,     dtype=torch.bool				).to(lowercase_				)

     # forward pass
     with torch.no_grad():
         snake_case_ :     Any				=	model(pixel_values=lowercase_  ,     bool_masked_pos=lowercase_				)
     snake_case_ :     int				=	outputs.logits

     # verify the logits
     snake_case_ :     Any				=	torch.Size((1, 196, 8192)				)
     self.assertEqual(logits.shape  ,     lowercase_				)

     snake_case_ :     Optional[int]				=	torch.tensor(
         [[-3.24_37, 0.50_72, -13.91_74], [-3.24_56, 0.49_48, -13.94_01], [-3.20_33, 0.51_21, -13.85_50]]				).to(lowercase_				)

     self.assertTrue(torch.allclose(logits[bool_masked_pos][:3, :3]  ,     lowercase_  ,     atol=1E-2				)				)

 @slow
 def 						_snake_case					(     self		:       int				):
     snake_case_ :     List[str]				=	BeitForImageClassification.from_pretrained('''microsoft/beit-base-patch16-224'''				).to(lowercase_				)

     snake_case_ :     Dict				=	self.default_image_processor
     snake_case_ :     Tuple				=	prepare_img()
     snake_case_ :     str				=	image_processor(images=lowercase_  ,     return_tensors='''pt'''				).to(lowercase_				)

     # forward pass
     with torch.no_grad():
         snake_case_ :     Union[str, Any]				=	model(**lowercase_				)
     snake_case_ :     int				=	outputs.logits

     # verify the logits
     snake_case_ :     Optional[Any]				=	torch.Size((1, 1000)				)
     self.assertEqual(logits.shape  ,     lowercase_				)

     snake_case_ :     Optional[int]				=	torch.tensor([-1.23_85, -1.09_87, -1.01_08]				).to(lowercase_				)

     self.assertTrue(torch.allclose(logits[0, :3]  ,     lowercase_  ,     atol=1E-4				)				)

     snake_case_ :     List[Any]				=	281
     self.assertEqual(logits.argmax(-1				).item()  ,     lowercase_				)

 @slow
 def 						_snake_case					(     self		:       Any				):
     snake_case_ :     int				=	BeitForImageClassification.from_pretrained('''microsoft/beit-large-patch16-224-pt22k-ft22k'''				).to(
         lowercase_				)

     snake_case_ :     List[Any]				=	self.default_image_processor
     snake_case_ :     Optional[Any]				=	prepare_img()
     snake_case_ :     Optional[Any]				=	image_processor(images=lowercase_  ,     return_tensors='''pt'''				).to(lowercase_				)

     # forward pass
     with torch.no_grad():
         snake_case_ :     Any				=	model(**lowercase_				)
     snake_case_ :     Union[str, Any]				=	outputs.logits

     # verify the logits
     snake_case_ :     Tuple				=	torch.Size((1, 21841)				)
     self.assertEqual(logits.shape  ,     lowercase_				)

     snake_case_ :     List[str]				=	torch.tensor([1.68_81, -0.27_87, 0.59_01]				).to(lowercase_				)

     self.assertTrue(torch.allclose(logits[0, :3]  ,     lowercase_  ,     atol=1E-4				)				)

     snake_case_ :     List[str]				=	2396
     self.assertEqual(logits.argmax(-1				).item()  ,     lowercase_				)

 @slow
 def 						_snake_case					(     self		:       int				):
     snake_case_ :     Union[str, Any]				=	BeitForSemanticSegmentation.from_pretrained('''microsoft/beit-base-finetuned-ade-640-640'''				)
     snake_case_ :     List[Any]				=	model.to(lowercase_				)

     snake_case_ :     Tuple				=	BeitImageProcessor(do_resize=lowercase_  ,     size=640  ,     do_center_crop=lowercase_				)

     snake_case_ :     Tuple				=	load_dataset('''hf-internal-testing/fixtures_ade20k'''  ,     split='''test'''				)
     snake_case_ :     Tuple				=	Image.open(ds[0]['''file''']				)
     snake_case_ :     List[str]				=	image_processor(images=lowercase_  ,     return_tensors='''pt'''				).to(lowercase_				)

     # forward pass
     with torch.no_grad():
         snake_case_ :     Any				=	model(**lowercase_				)
     snake_case_ :     Tuple				=	outputs.logits

     # verify the logits
     snake_case_ :     List[str]				=	torch.Size((1, 150, 160, 160)				)
     self.assertEqual(logits.shape  ,     lowercase_				)

     snake_case_ :     Optional[Any]				=	version.parse(PIL.__version__				) < version.parse('''9.0.0'''				)

     if is_pillow_less_than_a:
         snake_case_ :     Dict				=	torch.tensor(
             [
                 [[-4.92_25, -2.39_54, -3.05_22], [-2.88_22, -1.00_46, -1.75_61], [-2.95_49, -1.32_28, -2.13_47]],
                 [[-5.81_68, -3.41_29, -4.07_78], [-3.86_51, -2.22_14, -3.02_77], [-3.83_56, -2.46_43, -3.35_35]],
                 [[-0.00_78, 3.99_52, 4.07_54], [2.98_56, 4.69_44, 5.00_35], [3.24_13, 4.78_13, 4.99_69]],
             ]  ,     device=lowercase_  ,     )
     else:
         snake_case_ :     List[str]				=	torch.tensor(
             [
                 [[-4.89_60, -2.36_88, -3.03_55], [-2.84_78, -0.98_36, -1.74_18], [-2.94_49, -1.33_32, -2.14_56]],
                 [[-5.80_81, -3.41_24, -4.10_06], [-3.85_61, -2.20_81, -3.03_23], [-3.83_65, -2.46_01, -3.36_69]],
                 [[-0.03_09, 3.98_68, 4.05_40], [2.96_40, 4.68_77, 4.99_76], [3.20_81, 4.76_90, 4.99_42]],
             ]  ,     device=lowercase_  ,     )

     self.assertTrue(torch.allclose(logits[0, :3, :3, :3]  ,     lowercase_  ,     atol=1E-4				)				)






 @slow
 def 						_snake_case					(     self		:       int				):
     snake_case_ :     Optional[int]				=	BeitForSemanticSegmentation.from_pretrained('''microsoft/beit-base-finetuned-ade-640-640'''				)
     snake_case_ :     List[str]				=	model.to(lowercase_				)

     snake_case_ :     List[str]				=	BeitImageProcessor(do_resize=lowercase_  ,     size=640  ,     do_center_crop=lowercase_				)

     snake_case_ :     List[str]				=	load_dataset('''hf-internal-testing/fixtures_ade20k'''  ,     split='''test'''				)
     snake_case_ :     Tuple				=	Image.open(ds[0]['''file''']				)
     snake_case_ :     Tuple				=	image_processor(images=lowercase_  ,     return_tensors='''pt'''				).to(lowercase_				)

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

     snake_case_ :     Dict				=	outputs.logits.detach().cpu()

     snake_case_ :     Optional[Any]				=	image_processor.post_process_semantic_segmentation(outputs=lowercase_  ,     target_sizes=[(500, 300)]				)
     snake_case_ :     List[str]				=	torch.Size((500, 300)				)
     self.assertEqual(segmentation[0].shape  ,     lowercase_				)

     snake_case_ :     List[str]				=	image_processor.post_process_semantic_segmentation(outputs=lowercase_				)
     snake_case_ :     Any				=	torch.Size((160, 160)				)
     self.assertEqual(segmentation[0].shape  ,     lowercase_				)









'''simple docstring'''







class A__       :






      def __init__( self			:List[str]	)       ->					List[Any]:




             '''simple docstring'''
             _a    : Tuple     					=0
             _a    : Any     					=0
             _a    : int     					={}






      def __UpperCAmelCase       ( self			:Any     ,						SCREAMING_SNAKE_CASE			:List[str]	)       ->					Optional[int]:




             '''simple docstring'''
             if vertex not in self.adjacency:
                    _a    : Dict     					={}
                    self.num_vertices += 1






      def __UpperCAmelCase       ( self			:Optional[Any]     ,						SCREAMING_SNAKE_CASE			:str     ,						SCREAMING_SNAKE_CASE			:str     ,						SCREAMING_SNAKE_CASE			:Any	)       ->					List[str]:




             '''simple docstring'''
             self.add_vertex(SCREAMING_SNAKE_CASE	)
             self.add_vertex(SCREAMING_SNAKE_CASE	)

             if head == tail:
                    return

             _a    : Any     					=weight
             _a    : Tuple     					=weight






      def __UpperCAmelCase       ( self			:Dict	)       ->					Optional[int]:




             '''simple docstring'''
             _a    : Union[str, Any]     					=self.get_edges()
             for edge in edges:
                    _a					,    _a					,    _a    : List[str]     					=edge
                    edges.remove((tail, head, weight)	)
             for i in range(len(SCREAMING_SNAKE_CASE	)	):
                    _a    : str     					=list(edges[i]	)

             edges.sort(key=lambda SCREAMING_SNAKE_CASE	: e[2]	)
             for i in range(len(SCREAMING_SNAKE_CASE	) - 1	):
                    if edges[i][2] >= edges[i + 1][2]:
                           _a    : Union[str, Any]     					=edges[i][2] + 1
             for edge in edges:
                    _a					,    _a					,    _a    : Tuple     					=edge
                    _a    : Tuple     					=weight
                    _a    : List[Any]     					=weight






      def __str__( self			:int	)       ->					str:




             '''simple docstring'''
             _a    : int     					=""""""
             for tail in self.adjacency:
                    for head in self.adjacency[tail]:
                           _a    : str     					=self.adjacency[head][tail]
                           string += f"{head} -> {tail} == {weight}\n"
             return string.rstrip("""\n"""	)






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




             '''simple docstring'''
             _a    : Union[str, Any]     					=[]
             for tail in self.adjacency:
                    for head in self.adjacency[tail]:
                           output.append((tail, head, self.adjacency[head][tail])	)
             return output






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




             '''simple docstring'''
             return self.adjacency.keys()






      @staticmethod
      def __UpperCAmelCase       ( SCREAMING_SNAKE_CASE			:Dict=None     ,						SCREAMING_SNAKE_CASE			:List[Any]=None	)       ->					Optional[int]:




             '''simple docstring'''
             _a    : str     					=Graph()
             if vertices is None:
                    _a    : Union[str, Any]     					=[]
             if edges is None:
                    _a    : List[Any]     					=[]
             for vertex in vertices:
                    g.add_vertex(SCREAMING_SNAKE_CASE	)
             for edge in edges:
                    g.add_edge(*SCREAMING_SNAKE_CASE	)
             return g







      class A__       :






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




                   '''simple docstring'''
                   _a    : Optional[int]     					={}
                   _a    : List[str]     					={}






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




                   '''simple docstring'''
                   return len(self.parent	)






            def __UpperCAmelCase       ( self			:Tuple     ,						SCREAMING_SNAKE_CASE			:Tuple	)       ->					Dict:




                   '''simple docstring'''
                   if item in self.parent:
                          return self.find(SCREAMING_SNAKE_CASE	)

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






            def __UpperCAmelCase       ( self			:int     ,						SCREAMING_SNAKE_CASE			:Dict	)       ->					List[str]:




                   '''simple docstring'''
                   if item not in self.parent:
                          return self.make_set(SCREAMING_SNAKE_CASE	)
                   if item != self.parent[item]:
                          _a    : str     					=self.find(self.parent[item]	)
                   return self.parent[item]






            def __UpperCAmelCase       ( self			:Optional[int]     ,						SCREAMING_SNAKE_CASE			:Tuple     ,						SCREAMING_SNAKE_CASE			:List[Any]	)       ->					Optional[Any]:




                   '''simple docstring'''
                   _a    : Optional[int]     					=self.find(SCREAMING_SNAKE_CASE	)
                   _a    : Dict     					=self.find(SCREAMING_SNAKE_CASE	)

                   if roota == roota:
                          return roota

                   if self.rank[roota] > self.rank[roota]:
                          _a    : Any     					=roota
                          return roota

                   if self.rank[roota] < self.rank[roota]:
                          _a    : List[str]     					=roota
                          return roota

                   if self.rank[roota] == self.rank[roota]:
                          self.rank[roota] += 1
                          _a    : List[Any]     					=roota
                          return roota
                   return None






      @staticmethod
      def __UpperCAmelCase       ( SCREAMING_SNAKE_CASE			:Dict	)       ->					Union[str, Any]:




             '''simple docstring'''
             _a    : Any     					=graph.num_vertices

             _a    : Union[str, Any]     					=Graph.UnionFind()
             _a    : Optional[int]     					=[]
             while num_components > 1:
                    _a    : str     					={}
                    for vertex in graph.get_vertices():
                           _a    : List[str]     					=-1

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

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


