


import math
import os
import unittest

from transformers import MegatronBertConfig, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_sentencepiece, require_tokenizers, require_torch, slow, torch_device

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


if is_torch_available():
	import torch

	from transformers import (
	    MODEL_FOR_PRETRAINING_MAPPING,
	    MegatronBertForCausalLM,
	    MegatronBertForMaskedLM,
	    MegatronBertForMultipleChoice,
	    MegatronBertForNextSentencePrediction,
	    MegatronBertForPreTraining,
	    MegatronBertForQuestionAnswering,
	    MegatronBertForSequenceClassification,
	    MegatronBertForTokenClassification,
	    MegatronBertModel,
	)






class     UpperCamelCase:


					def __init__(						self	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[Any]=1_3     ,    SCREAMING_SNAKE_CASE	:		Optional[int]=7     ,    SCREAMING_SNAKE_CASE	:		Tuple=True     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]=True     ,    SCREAMING_SNAKE_CASE	:		List[Any]=True     ,    SCREAMING_SNAKE_CASE	:		str=True     ,    SCREAMING_SNAKE_CASE	:		Tuple=9_9     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]=6_4     ,    SCREAMING_SNAKE_CASE	:		Tuple=3_2     ,    SCREAMING_SNAKE_CASE	:		Optional[int]=5     ,    SCREAMING_SNAKE_CASE	:		int=4     ,    SCREAMING_SNAKE_CASE	:		Optional[int]=3_7     ,    SCREAMING_SNAKE_CASE	:		str="gelu"     ,    SCREAMING_SNAKE_CASE	:		List[str]=0.1     ,    SCREAMING_SNAKE_CASE	:		str=0.1     ,    SCREAMING_SNAKE_CASE	:		List[Any]=5_1_2     ,    SCREAMING_SNAKE_CASE	:		str=1_6     ,    SCREAMING_SNAKE_CASE	:		int=2     ,    SCREAMING_SNAKE_CASE	:		List[str]=0.02     ,    SCREAMING_SNAKE_CASE	:		List[Any]=3     ,    SCREAMING_SNAKE_CASE	:		Optional[int]=4     ,    SCREAMING_SNAKE_CASE	:		Tuple=None     ,    )			->	List[Any]:




											'''simple docstring'''

											__snake_case				=		parent
											__snake_case				=		batch_size
											__snake_case				=		seq_length
											__snake_case				=		is_training
											__snake_case				=		use_input_mask
											__snake_case				=		use_token_type_ids
											__snake_case				=		use_labels
											__snake_case				=		vocab_size
											__snake_case				=		hidden_size
											__snake_case				=		embedding_size
											__snake_case				=		num_hidden_layers
											__snake_case				=		num_attention_heads
											__snake_case				=		intermediate_size
											__snake_case				=		hidden_act
											__snake_case				=		hidden_dropout_prob
											__snake_case				=		attention_probs_dropout_prob
											__snake_case				=		max_position_embeddings
											__snake_case				=		type_vocab_size
											__snake_case				=		type_sequence_label_size
											__snake_case				=		initializer_range
											__snake_case				=		num_labels
											__snake_case				=		num_choices
											__snake_case				=		scope


					def 							SCREAMING_SNAKE_CASE_  (						self	:		int						)			->	Dict:




											'''simple docstring'''

											__snake_case				=		ids_tensor([self.batch_size, self.seq_length]     ,    self.vocab_size						)

											__snake_case				=		None
											if self.use_input_mask:
																	__snake_case				=		random_attention_mask([self.batch_size, self.seq_length]						)

											__snake_case				=		None
											if self.use_token_type_ids:
																	__snake_case				=		ids_tensor([self.batch_size, self.seq_length]     ,    self.type_vocab_size						)

											__snake_case				=		None
											__snake_case				=		None
											__snake_case				=		None
											if self.use_labels:
																	__snake_case				=		ids_tensor([self.batch_size]     ,    self.type_sequence_label_size						)
																	__snake_case				=		ids_tensor([self.batch_size, self.seq_length]     ,    self.num_labels						)
																	__snake_case				=		ids_tensor([self.batch_size]     ,    self.num_choices						)

											__snake_case				=		self.get_config()

											return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels


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




											'''simple docstring'''

											return MegatronBertConfig(
											    vocab_size=self.vocab_size     ,    hidden_size=self.hidden_size     ,    num_hidden_layers=self.num_hidden_layers     ,    num_attention_heads=self.num_attention_heads     ,    intermediate_size=self.intermediate_size     ,    embedding_size=self.embedding_size     ,    hidden_act=self.hidden_act     ,    hidden_dropout_prob=self.hidden_dropout_prob     ,    attention_probs_dropout_prob=self.attention_probs_dropout_prob     ,    max_position_embeddings=self.max_position_embeddings     ,    type_vocab_size=self.type_vocab_size     ,    is_decoder=__A     ,    initializer_range=self.initializer_range     ,    )


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




											'''simple docstring'''

											__snake_case				=		MegatronBertModel(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(__A     ,    attention_mask=__A     ,    token_type_ids=__A						)
											__snake_case				=		model(__A     ,    token_type_ids=__A						)
											__snake_case				=		model(__A						)

											self.parent.assertEqual(result.last_hidden_state.shape     ,    (self.batch_size, self.seq_length, self.hidden_size)						)
											self.parent.assertEqual(result.pooler_output.shape     ,    (self.batch_size, self.hidden_size)						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		Any     ,    SCREAMING_SNAKE_CASE	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		int     ,    SCREAMING_SNAKE_CASE	:		int						)			->	Any:




											'''simple docstring'''

											__snake_case				=		MegatronBertForMaskedLM(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(__A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    labels=__A						)
											self.parent.assertEqual(result.logits.shape     ,    (self.batch_size, self.seq_length, self.vocab_size)						)


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




											'''simple docstring'''

											__snake_case				=		MegatronBertForCausalLM(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(__A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    labels=__A						)
											self.parent.assertEqual(result.logits.shape     ,    (self.batch_size, self.seq_length, self.vocab_size)						)


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




											'''simple docstring'''

											__snake_case				=		MegatronBertForNextSentencePrediction(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(
											    __A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    labels=__A     ,    )
											self.parent.assertEqual(result.logits.shape     ,    (self.batch_size, 2)						)


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




											'''simple docstring'''

											__snake_case				=		MegatronBertForPreTraining(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(
											    __A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    labels=__A     ,    next_sentence_label=__A     ,    )
											self.parent.assertEqual(result.prediction_logits.shape     ,    (self.batch_size, self.seq_length, self.vocab_size)						)
											self.parent.assertEqual(result.seq_relationship_logits.shape     ,    (self.batch_size, 2)						)


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




											'''simple docstring'''

											__snake_case				=		MegatronBertForQuestionAnswering(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(
											    __A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    start_positions=__A     ,    end_positions=__A     ,    )
											self.parent.assertEqual(result.start_logits.shape     ,    (self.batch_size, self.seq_length)						)
											self.parent.assertEqual(result.end_logits.shape     ,    (self.batch_size, self.seq_length)						)


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




											'''simple docstring'''

											__snake_case				=		self.num_labels
											__snake_case				=		MegatronBertForSequenceClassification(__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(__A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    labels=__A						)
											self.parent.assertEqual(result.logits.shape     ,    (self.batch_size, self.num_labels)						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		List[str]						)			->	Dict:




											'''simple docstring'''

											__snake_case				=		self.num_labels
											__snake_case				=		MegatronBertForTokenClassification(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		model(__A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    labels=__A						)
											self.parent.assertEqual(result.logits.shape     ,    (self.batch_size, self.seq_length, self.num_labels)						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict     ,    SCREAMING_SNAKE_CASE	:		str     ,    SCREAMING_SNAKE_CASE	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Dict     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Dict						)			->	Union[str, Any]:




											'''simple docstring'''

											__snake_case				=		self.num_choices
											__snake_case				=		MegatronBertForMultipleChoice(config=__A						)
											model.to(__A						)
											model.eval()
											__snake_case				=		input_ids.unsqueeze(1						).expand(-1     ,    self.num_choices     ,    -1						).contiguous()
											__snake_case				=		token_type_ids.unsqueeze(1						).expand(-1     ,    self.num_choices     ,    -1						).contiguous()
											__snake_case				=		input_mask.unsqueeze(1						).expand(-1     ,    self.num_choices     ,    -1						).contiguous()
											__snake_case				=		model(
											    __A     ,    attention_mask=__A     ,    token_type_ids=__A     ,    labels=__A     ,    )
											self.parent.assertEqual(result.logits.shape     ,    (self.batch_size, self.num_choices)						)






					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict						)			->	List[Any]:




											'''simple docstring'''

											__snake_case				=		self.prepare_config_and_inputs()
											(
											    (
											    __snake_case						
											)		,					(
											    __snake_case						
											)		,					(
											    __snake_case						
											)		,					(
											    __snake_case						
											)		,					(
											    __snake_case						
											)		,					(
											    __snake_case						
											)		,					(
											    __snake_case						
											)		,											
											)				=		config_and_inputs
											__snake_case				=		{"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
											return config, inputs_dict






@require_torch
class     UpperCamelCase(  UpperCamelCase__     ,							UpperCamelCase__     ,							unittest.TestCase   ):
					snake_case_		:				List[Any]										=	(
					    (
					        MegatronBertModel,
					        MegatronBertForMaskedLM,
					        MegatronBertForCausalLM,
					        MegatronBertForMultipleChoice,
					        MegatronBertForNextSentencePrediction,
					        MegatronBertForPreTraining,
					        MegatronBertForQuestionAnswering,
					        MegatronBertForSequenceClassification,
					        MegatronBertForTokenClassification,
					    )
					    if is_torch_available()
					    else ()
					)
					snake_case_		:				int										=	(
					    {
					        """feature-extraction""": MegatronBertModel,
					        """fill-mask""": MegatronBertForMaskedLM,
					        """question-answering""": MegatronBertForQuestionAnswering,
					        """text-classification""": MegatronBertForSequenceClassification,
					        """text-generation""": MegatronBertForCausalLM,
					        """token-classification""": MegatronBertForTokenClassification,
					        """zero-shot""": MegatronBertForSequenceClassification,
					    }
					    if is_torch_available()
					    else {}
					)
					snake_case_		:				List[str]										=	True
					# test_resize_embeddings = False
					snake_case_		:				Tuple										=	False


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		List[Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[int]=False						)			->	List[Any]:




											'''simple docstring'''

											__snake_case				=		super()._prepare_for_class(__A     ,    __A     ,    return_labels=__A						)

											if return_labels:
																	if model_class in get_values(__A						):
																							__snake_case				=		torch.zeros(
																							    (self.model_tester.batch_size, self.model_tester.seq_length)     ,    dtype=torch.long     ,    device=__A						)
																							__snake_case				=		torch.zeros(
																							    self.model_tester.batch_size     ,    dtype=torch.long     ,    device=__A						)
											return inputs_dict


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[int]						)			->	str:




											'''simple docstring'''

											__snake_case				=		MegatronBertModelTester(self						)
											__snake_case				=		ConfigTester(self     ,    config_class=__A     ,    hidden_size=3_7						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]						)			->	Dict:




											'''simple docstring'''

											self.config_tester.run_common_tests()


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




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_model(*__A						)


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




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_for_masked_lm(*__A						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]						)			->	Any:




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_for_multiple_choice(*__A						)


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




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_for_next_sequence_prediction(*__A						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[Any]						)			->	Tuple:




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_for_pretraining(*__A						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]						)			->	Dict:




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_for_question_answering(*__A						)


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




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_for_sequence_classification(*__A						)






					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict						)			->	int:




											'''simple docstring'''

											__snake_case				=		self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_megatron_bert_for_token_classification(*__A						)





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	Tuple:


						'''simple docstring'''






						return torch.tensor(
						    UpperCamelCase__      ,	dtype=torch.long      ,	device=UpperCamelCase__      ,	)


A							:					Union[str, Any]     						=     1E-4






@require_torch
@require_sentencepiece
@require_tokenizers
class     UpperCamelCase(  unittest.TestCase   ):


					@slow
					@unittest.skip("Model is not available."						)
					def 							SCREAMING_SNAKE_CASE_  (						self	:		str						)			->	List[Any]:




											'''simple docstring'''

											__snake_case				=		"nvidia/megatron-bert-uncased-345m"
											if "MYDIR" in os.environ:
																	__snake_case				=		os.path.join(os.environ["MYDIR"]     ,    __A						)
											__snake_case				=		MegatronBertModel.from_pretrained(__A						)
											model.to(__A						)
											model.half()
											__snake_case				=		_long_tensor([[1_0_1, 7_1_1_0, 1_0_0_5, 1_0_5_6, 2_0_2_3, 1_1_3_3_3, 1_7_4_1_3, 1_0_2_9, 1_0_2]]						)
											with torch.no_grad():
																	__snake_case				=		model(__A						)[0]
											__snake_case				=		torch.Size((1, 9, 1_0_2_4)						)
											self.assertEqual(output.shape     ,    __A						)

											__snake_case				=		[-0.6040, -0.2517, -0.1025, 0.3420, -0.6758, -0.0017, -0.1089, -0.1990, 0.5728]
											for ii in range(3						):
																	for jj in range(3						):
																							__snake_case				=		output[0, ii, jj]
																							__snake_case				=		expected[3 * ii + jj]
																							__snake_case				=		"ii={} jj={} a={} b={}".format(__A     ,    __A     ,    __A     ,    __A						)
																							self.assertTrue(math.isclose(__A     ,    __A     ,    rel_tol=__A     ,    abs_tol=__A						)     ,    msg=__A						)









class     UpperCamelCase:


					def __init__(						self	:		Any						)			->	Any:




											'''simple docstring'''

											__snake_case				=		0
											__snake_case				=		0
											__snake_case				=		{}


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict     ,    SCREAMING_SNAKE_CASE	:		Optional[int]						)			->	Optional[Any]:




											'''simple docstring'''

											if vertex not in self.adjacency:
																	__snake_case				=		{}
																	self.num_vertices += 1


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




											'''simple docstring'''

											self.add_vertex(SCREAMING_SNAKE_CASE						)
											self.add_vertex(SCREAMING_SNAKE_CASE						)

											if head == tail:
																	return

											__snake_case				=		weight
											__snake_case				=		weight


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[int]						)			->	Tuple:




											'''simple docstring'''

											__snake_case				=		self.get_edges()
											for edge in edges:
																	__snake_case		,					__snake_case		,					__snake_case				=		edge
																	edges.remove((tail, head, weight)						)
											for i in range(len(SCREAMING_SNAKE_CASE						)						):
																	__snake_case				=		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]:
																							__snake_case				=		edges[i][2] + 1
											for edge in edges:
																	__snake_case		,					__snake_case		,					__snake_case				=		edge
																	__snake_case				=		weight
																	__snake_case				=		weight


					def __str__(						self	:		Tuple						)			->	List[Any]:




											'''simple docstring'''

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


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




											'''simple docstring'''

											__snake_case				=		[]
											for tail in self.adjacency:
																	for head in self.adjacency[tail]:
																							output.append((tail, head, self.adjacency[head][tail])						)
											return output


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




											'''simple docstring'''

											return self.adjacency.keys()


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




											'''simple docstring'''

											__snake_case				=		Graph()
											if vertices is None:
																	__snake_case				=		[]
											if edges is None:
																	__snake_case				=		[]
											for vertex in vertices:
																	g.add_vertex(SCREAMING_SNAKE_CASE						)
											for edge in edges:
																	g.add_edge(*SCREAMING_SNAKE_CASE						)
											return g






					class     UpperCamelCase:


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




																'''simple docstring'''

																__snake_case				=		{}
																__snake_case				=		{}


										def __len__(						self	:		List[str]						)			->	Dict:




																'''simple docstring'''

																return len(self.parent						)


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




																'''simple docstring'''

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

																__snake_case				=		item
																__snake_case				=		0
																return item


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




																'''simple docstring'''

																if item not in self.parent:
																						return self.make_set(SCREAMING_SNAKE_CASE						)
																if item != self.parent[item]:
																						__snake_case				=		self.find(self.parent[item]						)
																return self.parent[item]






										def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		int     ,    SCREAMING_SNAKE_CASE	:		Union[str, Any]						)			->	Dict:




																'''simple docstring'''

																__snake_case				=		self.find(SCREAMING_SNAKE_CASE						)
																__snake_case				=		self.find(SCREAMING_SNAKE_CASE						)

																if roota == roota:
																						return roota

																if self.rank[roota] > self.rank[roota]:
																						__snake_case				=		roota
																						return roota

																if self.rank[roota] < self.rank[roota]:
																						__snake_case				=		roota
																						return roota

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




					@staticmethod
					def 							SCREAMING_SNAKE_CASE_  (						SCREAMING_SNAKE_CASE	:		str						)			->	Any:




											'''simple docstring'''

											__snake_case				=		graph.num_vertices

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

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

																													if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																																			__snake_case				=		[head, tail, weight]
																	for vertex in cheap_edge:
																							if cheap_edge[vertex] != -1:
																													__snake_case		,					__snake_case		,					__snake_case				=		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]						)
																																			__snake_case				=		num_components - 1
											__snake_case				=		Graph.build(edges=SCREAMING_SNAKE_CASE						)
											return mst





