


'''simple docstring'''




import unittest

from transformers import ElectraConfig, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device

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


if is_torch_available():
				import torch

				from transformers import (
				    MODEL_FOR_PRETRAINING_MAPPING,
				    ElectraForCausalLM,
				    ElectraForMaskedLM,
				    ElectraForMultipleChoice,
				    ElectraForPreTraining,
				    ElectraForQuestionAnswering,
				    ElectraForSequenceClassification,
				    ElectraForTokenClassification,
				    ElectraModel,
				)
				from transformers.models.electra.modeling_electra import ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST





class _snake_case :
							"""simple docstring"""





							def __init__( self      ,					__A      ,					__A=13      ,					__A=7      ,					__A=True      ,					__A=True      ,					__A=True      ,					__A=True      ,					__A=99      ,					__A=32      ,					__A=5      ,					__A=4      ,					__A=37      ,					__A="gelu"      ,					__A=0.1      ,					__A=0.1      ,					__A=512      ,					__A=16      ,					__A=2      ,					__A=0.02      ,					__A=3      ,					__A=4      ,					__A=None      ,					)  ->Union[str, Any]:



											"""simple docstring"""







											__lowerCamelCase		:   int           =       parent
											__lowerCamelCase		:   Optional[Any]           =       batch_size
											__lowerCamelCase		:   Dict           =       seq_length
											__lowerCamelCase		:   List[Any]           =       is_training
											__lowerCamelCase		:   Tuple           =       use_input_mask
											__lowerCamelCase		:   str           =       use_token_type_ids
											__lowerCamelCase		:   Optional[Any]           =       use_labels
											__lowerCamelCase		:   Union[str, Any]           =       vocab_size
											__lowerCamelCase		:   str           =       hidden_size
											__lowerCamelCase		:   Union[str, Any]           =       num_hidden_layers
											__lowerCamelCase		:   Tuple           =       num_attention_heads
											__lowerCamelCase		:   List[Any]           =       intermediate_size
											__lowerCamelCase		:   Any           =       hidden_act
											__lowerCamelCase		:   Optional[Any]           =       hidden_dropout_prob
											__lowerCamelCase		:   Any           =       attention_probs_dropout_prob
											__lowerCamelCase		:   List[str]           =       max_position_embeddings
											__lowerCamelCase		:   Tuple           =       type_vocab_size
											__lowerCamelCase		:   Union[str, Any]           =       type_sequence_label_size
											__lowerCamelCase		:   Dict           =       initializer_range
											__lowerCamelCase		:   Tuple           =       num_labels
											__lowerCamelCase		:   Optional[Any]           =       num_choices
											__lowerCamelCase		:   Any           =       scope







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Optional[int]:



											"""simple docstring"""







											__lowerCamelCase		:   Optional[int]           =       ids_tensor([self.batch_size, self.seq_length]      ,					self.vocab_size						)

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

											__lowerCamelCase		:   Optional[Any]           =       None
											if self.use_token_type_ids:
															__lowerCamelCase		:   str           =       ids_tensor([self.batch_size, self.seq_length]      ,					self.type_vocab_size						)

											__lowerCamelCase		:   Optional[int]           =       None
											__lowerCamelCase		:   Dict           =       None
											__lowerCamelCase		:   Dict           =       None
											if self.use_labels:
															__lowerCamelCase		:   int           =       ids_tensor([self.batch_size]      ,					self.type_sequence_label_size						)
															__lowerCamelCase		:   List[Any]           =       ids_tensor([self.batch_size, self.seq_length]      ,					self.num_labels						)
															__lowerCamelCase		:   Union[str, Any]           =       ids_tensor([self.batch_size]      ,					self.num_choices						)
															__lowerCamelCase		:   str           =       ids_tensor([self.batch_size, self.seq_length]      ,					1						)

											__lowerCamelCase		:   Optional[int]           =       self.get_config()

											return (
											    config,
											    input_ids,
											    token_type_ids,
											    input_mask,
											    sequence_labels,
											    token_labels,
											    choice_labels,
											    fake_token_labels,
											)







							def 		__SCREAMING_SNAKE_CASE( self						)  ->int:



											"""simple docstring"""







											return ElectraConfig(
											    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      ,					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						)  ->Optional[Any]:



											"""simple docstring"""







											(
											    (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       
											)		:   Union[str, Any]           =       self.prepare_config_and_inputs()

											__lowerCamelCase		:   int           =       True
											__lowerCamelCase		:   Optional[Any]           =       floats_tensor([self.batch_size, self.seq_length, self.hidden_size]						)
											__lowerCamelCase		:   Optional[Any]           =       ids_tensor([self.batch_size, self.seq_length]      ,					vocab_size=2						)

											return (
											    config,
											    input_ids,
											    token_type_ids,
											    input_mask,
											    sequence_labels,
											    token_labels,
											    choice_labels,
											    encoder_hidden_states,
											    encoder_attention_mask,
											)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   List[Any]           =       ElectraModel(config=__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   Union[str, Any]           =       model(__A      ,					attention_mask=__A      ,					token_type_ids=__A						)
											__lowerCamelCase		:   Dict           =       model(__A      ,					token_type_ids=__A						)
											__lowerCamelCase		:   Optional[Any]           =       model(__A						)
											self.parent.assertEqual(result.last_hidden_state.shape      ,					(self.batch_size, self.seq_length, self.hidden_size)						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->List[str]:



											"""simple docstring"""







											__lowerCamelCase		:   List[str]           =       True
											__lowerCamelCase		:   Tuple           =       ElectraModel(__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   List[str]           =       model(
											    __A      ,					attention_mask=__A      ,					token_type_ids=__A      ,					encoder_hidden_states=__A      ,					encoder_attention_mask=__A      ,					)
											__lowerCamelCase		:   Dict           =       model(
											    __A      ,					attention_mask=__A      ,					token_type_ids=__A      ,					encoder_hidden_states=__A      ,					)
											__lowerCamelCase		:   Optional[Any]           =       model(__A      ,					attention_mask=__A      ,					token_type_ids=__A						)
											self.parent.assertEqual(result.last_hidden_state.shape      ,					(self.batch_size, self.seq_length, self.hidden_size)						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->str:



											"""simple docstring"""







											__lowerCamelCase		:   Union[str, Any]           =       ElectraForMaskedLM(config=__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   List[Any]           =       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      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->Optional[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Tuple           =       ElectraForCausalLM(config=__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   Union[str, Any]           =       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      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Union[str, Any]           =       self.num_labels
											__lowerCamelCase		:   Optional[int]           =       ElectraForTokenClassification(config=__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   Tuple           =       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      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Tuple           =       self.num_labels
											__lowerCamelCase		:   Tuple           =       ElectraForPreTraining(config=__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   List[str]           =       model(__A      ,					attention_mask=__A      ,					token_type_ids=__A      ,					labels=__A						)
											self.parent.assertEqual(result.logits.shape      ,					(self.batch_size, self.seq_length)						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->Optional[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   List[str]           =       self.num_labels
											__lowerCamelCase		:   Union[str, Any]           =       ElectraForSequenceClassification(__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   Tuple           =       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      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   List[str]           =       ElectraForQuestionAnswering(config=__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   Any           =       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      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					__A      ,					)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   Any           =       self.num_choices
											__lowerCamelCase		:   Optional[int]           =       ElectraForMultipleChoice(config=__A						)
											model.to(__A						)
											model.eval()
											__lowerCamelCase		:   List[str]           =       input_ids.unsqueeze(1						).expand(-1      ,					self.num_choices      ,					-1						).contiguous()
											__lowerCamelCase		:   Dict           =       token_type_ids.unsqueeze(1						).expand(-1      ,					self.num_choices      ,					-1						).contiguous()
											__lowerCamelCase		:   Optional[Any]           =       input_mask.unsqueeze(1						).expand(-1      ,					self.num_choices      ,					-1						).contiguous()
											__lowerCamelCase		:   Optional[Any]           =       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						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   Optional[int]           =       self.prepare_config_and_inputs()
											(
											    (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       (
											    __lowerCamelCase
											)    ,       
											)		:   int           =       config_and_inputs
											__lowerCamelCase		:   Dict           =       {"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
											return config, inputs_dict





@require_torch
class _snake_case (			a__     , a__     , unittest.TestCase ):
							"""simple docstring"""





							__a				       =  (
							    (
							        ElectraModel,
							        ElectraForPreTraining,
							        ElectraForMaskedLM,
							        ElectraForCausalLM,
							        ElectraForMultipleChoice,
							        ElectraForTokenClassification,
							        ElectraForSequenceClassification,
							        ElectraForQuestionAnswering,
							    )
							    if is_torch_available()
							    else ()
							)
							__a				       =  (
							    {
							        '''feature-extraction''': ElectraModel,
							        '''fill-mask''': ElectraForMaskedLM,
							        '''question-answering''': ElectraForQuestionAnswering,
							        '''text-classification''': ElectraForSequenceClassification,
							        '''text-generation''': ElectraForCausalLM,
							        '''token-classification''': ElectraForTokenClassification,
							        '''zero-shot''': ElectraForSequenceClassification,
							    }
							    if is_torch_available()
							    else {}
							)
							__a				       =  True







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A=False						)  ->str:



											"""simple docstring"""







											__lowerCamelCase		:   Tuple           =       super()._prepare_for_class(__A      ,					__A      ,					return_labels=__A						)

											if return_labels:
															if model_class in get_values(__A						):
																			__lowerCamelCase		:   Union[str, Any]           =       torch.zeros(
																			    (self.model_tester.batch_size, self.model_tester.seq_length)      ,					dtype=torch.long      ,					device=__A						)
											return inputs_dict







							def 		__SCREAMING_SNAKE_CASE( self						)  ->str:



											"""simple docstring"""







											__lowerCamelCase		:   Any           =       ElectraModelTester(self						)
											__lowerCamelCase		:   Union[str, Any]           =       ConfigTester(self      ,					config_class=__A      ,					hidden_size=37						)







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



											"""simple docstring"""







											self.config_tester.run_common_tests()







							def 		__SCREAMING_SNAKE_CASE( self						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   List[Any]           =       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_electra_model(*__A						)







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Optional[int]:



											"""simple docstring"""







											__lowerCamelCase		:   Any           =       self.model_tester.prepare_config_and_inputs_for_decoder()
											self.model_tester.create_and_check_electra_model_as_decoder(*__A						)







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Any:



											"""simple docstring"""







											__lowerCamelCase		:   str           =       self.model_tester.prepare_config_and_inputs()
											for type in ["absolute", "relative_key", "relative_key_query"]:
															__lowerCamelCase		:   Union[str, Any]           =       type
															self.model_tester.create_and_check_electra_model(*__A						)







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



											"""simple docstring"""







											__lowerCamelCase		:   Any           =       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_electra_for_masked_lm(*__A						)







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Dict:



											"""simple docstring"""







											__lowerCamelCase		:   Dict           =       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_electra_for_token_classification(*__A						)







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



											"""simple docstring"""







											__lowerCamelCase		:   List[Any]           =       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_electra_for_pretraining(*__A						)







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



											"""simple docstring"""







											__lowerCamelCase		:   int           =       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_electra_for_sequence_classification(*__A						)







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



											"""simple docstring"""







											__lowerCamelCase		:   Optional[int]           =       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_electra_for_question_answering(*__A						)







							def 		__SCREAMING_SNAKE_CASE( self						)  ->List[str]:



											"""simple docstring"""







											__lowerCamelCase		:   Optional[int]           =       self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_electra_for_multiple_choice(*__A						)







							@slow
							def 		__SCREAMING_SNAKE_CASE( self						)  ->Union[str, Any]:



											"""simple docstring"""







											for model_name in ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															__lowerCamelCase		:   Tuple           =       ElectraModel.from_pretrained(__A						)
															self.assertIsNotNone(__A						)







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



											"""simple docstring"""







											__lowerCamelCase		:   Optional[Any]           =       self.model_tester.prepare_config_and_inputs_for_decoder()
											self.model_tester.create_and_check_electra_for_causal_lm(*__A						)





@require_torch
class _snake_case (			unittest.TestCase ):
							"""simple docstring"""





							@slow
							def 		__SCREAMING_SNAKE_CASE( self						)  ->Optional[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Union[str, Any]           =       ElectraModel.from_pretrained("google/electra-small-discriminator"						)
											__lowerCamelCase		:   Dict           =       torch.tensor([[0, 345, 232, 328, 740, 140, 1695, 69, 6078, 1588, 2]]						)
											__lowerCamelCase		:   List[str]           =       torch.tensor([[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]						)
											__lowerCamelCase		:   str           =       model(__A      ,					attention_mask=__A						)[0]
											__lowerCamelCase		:   Tuple           =       torch.Size((1, 11, 256)						)
											self.assertEqual(output.shape      ,					__A						)
											__lowerCamelCase		:   Dict           =       torch.tensor(
											    [[[0.4471, 0.6821, -0.3265], [0.4627, 0.5255, -0.3668], [0.4532, 0.3313, -0.4344]]]						)

											self.assertTrue(torch.allclose(output[:, 1:4, 1:4]      ,					__A      ,					atol=1E-4						)						)









'''simple docstring'''




from collections import deque





def 				a_							(    lowercase     )      ->Tuple:






				'''simple docstring'''

				return input(lowercase     ).strip().split(" "     )





def 				a_							(    lowercase				,    lowercase     )      ->dict[int, list[int]]:






				'''simple docstring'''

				__lowerCamelCase		:   dict[int, list[int]]           =       {}
				for i in range(lowercase     ):
								__lowerCamelCase		:   int           =       []

				for e in range(lowercase     ):
								__lowerCamelCase    ,       __lowerCamelCase		:   int           =       (int(lowercase     ) for i in _input(F'Edge {e + 1}: <node1> <node2> '     ))
								graph[x].append(lowercase     )
				return graph





def 				a_							(    lowercase				,    lowercase     )      ->dict[int, list[int]]:






				'''simple docstring'''

				__lowerCamelCase		:   dict[int, list[int]]           =       {}
				for i in range(lowercase     ):
								__lowerCamelCase		:   Any           =       []

				for e in range(lowercase     ):
								__lowerCamelCase    ,       __lowerCamelCase		:   Dict           =       (int(lowercase     ) for i in _input(F'Edge {e + 1}: <node1> <node2> '     ))
								graph[x].append(lowercase     )
								graph[y].append(lowercase     )
				return graph





def 				a_							(    lowercase				,    lowercase     )      ->dict[int, list[tuple[int, int]]]:






				'''simple docstring'''

				__lowerCamelCase		:   dict[int, list[tuple[int, int]]]           =       {}
				for i in range(lowercase     ):
								__lowerCamelCase		:   List[Any]           =       []

				for e in range(lowercase     ):
								__lowerCamelCase    ,       __lowerCamelCase    ,       __lowerCamelCase		:   int           =       (int(lowercase     ) for i in _input(F'Edge {e + 1}: <node1> <node2> <weight> '     ))
								graph[x].append((y, w)     )
								graph[y].append((x, w)     )
				return graph


if __name__ == "__main__":
				__lowercase		,		__lowercase	:   List[Any]   		=					(int(i) for i in _input("""Number of nodes and edges: """))

				__lowercase	:   Any   		=					int(
				    _input(
				        """Press 1 or 2 or 3 \n"""
				        """1. Unweighted directed \n"""
				        """2. Unweighted undirected \n"""
				        """3. Weighted undirected \n"""
				    )[0]
				)

				__lowercase	:   Any   		=					{
				    1: initialize_unweighted_directed_graph,
				    2: initialize_unweighted_undirected_graph,
				    3: initialize_weighted_undirected_graph,
				}[graph_choice](n, m)





def 				a_							(    lowercase				,    lowercase     )      ->Tuple:






				'''simple docstring'''

				__lowerCamelCase    ,       __lowerCamelCase		:   Dict           =       {s}, [s]
				print(lowercase     )
				while _s:
								__lowerCamelCase		:   int           =       0
								for i in g[_s[-1]]:
												if i not in vis:
																_s.append(lowercase     )
																vis.add(lowercase     )
																__lowerCamelCase		:   Tuple           =       1
																print(lowercase     )
																break
								if not flag:
												_s.pop()





def 				a_							(    lowercase				,    lowercase     )      ->List[str]:






				'''simple docstring'''

				__lowerCamelCase    ,       __lowerCamelCase		:   Tuple           =       {s}, deque([s]     )
				print(lowercase     )
				while q:
								__lowerCamelCase		:   Optional[Any]           =       q.popleft()
								for v in g[u]:
												if v not in vis:
																vis.add(lowercase     )
																q.append(lowercase     )
																print(lowercase     )





def 				a_							(    lowercase				,    lowercase     )      ->Any:






				'''simple docstring'''

				__lowerCamelCase    ,       __lowerCamelCase    ,       __lowerCamelCase		:   Optional[int]           =       {s: 0}, set(), {s: 0}
				while True:
								if len(lowercase     ) == len(lowercase     ) - 1:
												break
								__lowerCamelCase		:   str           =       10_0000
								for i in dist:
												if i not in known and dist[i] < mini:
																__lowerCamelCase		:   Any           =       dist[i]
																__lowerCamelCase		:   List[str]           =       i
								known.add(lowercase     )
								for v in g[u]:
												if v[0] not in known and dist[u] + v[1] < dist.get(v[0]				,    10_0000     ):
																__lowerCamelCase		:   Optional[int]           =       dist[u] + v[1]
																__lowerCamelCase		:   List[str]           =       u
				for i in dist:
								if i != s:
												print(dist[i]     )





def 				a_							(    lowercase				,    lowercase=None				,    lowercase=None     )      ->Optional[Any]:






				'''simple docstring'''

				if q is None:
								__lowerCamelCase		:   int           =       [1]
				if ind is None:
								__lowerCamelCase		:   Any           =       [0] * (len(lowercase     ) + 1)  # SInce oth Index is ignored
								for u in g:
												for v in g[u]:
																ind[v] += 1
								__lowerCamelCase		:   Tuple           =       deque()
								for i in g:
												if ind[i] == 0:
																q.append(lowercase     )
				if len(lowercase     ) == 0:
								return
				__lowerCamelCase		:   Optional[Any]           =       q.popleft()
				print(lowercase     )
				for w in g[v]:
								ind[w] -= 1
								if ind[w] == 0:
												q.append(lowercase     )
				topo(lowercase				,    lowercase				,    lowercase     )





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






				'''simple docstring'''

				__lowerCamelCase		:   Tuple           =       input().strip()
				__lowerCamelCase		:   Any           =       []
				for _ in range(lowercase     ):
								a.append(map(lowercase				,    input().strip().split()     )     )
				return a, n





def 				a_							(    lowercase     )      ->List[str]:






				'''simple docstring'''

				((__lowerCamelCase)    ,       (__lowerCamelCase))		:   Optional[int]           =       a_and_n
				__lowerCamelCase		:   Optional[int]           =       list(lowercase     )
				__lowerCamelCase		:   str           =       [[0] * n for i in range(lowercase     )]
				for k in range(lowercase     ):
								for i in range(lowercase     ):
												for j in range(lowercase     ):
																if dist[i][j] > dist[i][k] + dist[k][j]:
																				__lowerCamelCase		:   str           =       dist[i][k] + dist[k][j]
																				__lowerCamelCase		:   Tuple           =       k
				print(lowercase     )





def 				a_							(    lowercase				,    lowercase     )      ->Dict:






				'''simple docstring'''

				__lowerCamelCase    ,       __lowerCamelCase    ,       __lowerCamelCase		:   int           =       {s: 0}, set(), {s: 0}
				while True:
								if len(lowercase     ) == len(lowercase     ) - 1:
												break
								__lowerCamelCase		:   List[Any]           =       10_0000
								for i in dist:
												if i not in known and dist[i] < mini:
																__lowerCamelCase		:   str           =       dist[i]
																__lowerCamelCase		:   Optional[int]           =       i
								known.add(lowercase     )
								for v in g[u]:
												if v[0] not in known and v[1] < dist.get(v[0]				,    10_0000     ):
																__lowerCamelCase		:   Dict           =       v[1]
																__lowerCamelCase		:   List[str]           =       u
				return dist





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






				'''simple docstring'''

				__lowerCamelCase    ,       __lowerCamelCase		:   List[Any]           =       map(lowercase				,    input().split(" "     )     )
				__lowerCamelCase		:   Optional[Any]           =       []
				for _ in range(lowercase     ):
								edges.append(map(lowercase				,    input().split(" "     )     )     )
				return edges, n





def 				a_							(    lowercase     )      ->Optional[int]:






				'''simple docstring'''

				((__lowerCamelCase)    ,       (__lowerCamelCase))		:   Any           =       e_and_n
				e.sort(reverse=lowercase				,    key=lambda lowercase     : x[2]     )
				__lowerCamelCase		:   Optional[Any]           =       [{i} for i in range(1				,    n + 1     )]
				while True:
								if len(lowercase     ) == 1:
												break
								print(lowercase     )
								__lowerCamelCase		:   List[str]           =       e.pop()
								for i in range(len(lowercase     )     ):
												if x[0] in s[i]:
																break
								for j in range(len(lowercase     )     ):
												if x[1] in s[j]:
																if i == j:
																				break
																s[j].update(s[i]     )
																s.pop(lowercase     )
																break





def 				a_							(    lowercase     )      ->int:






				'''simple docstring'''

				__lowerCamelCase		:   Tuple           =       []
				for node in graph:
								if not graph[node]:
												isolated.append(lowercase     )
				return isolated





