






"""simple docstring"""


from collections import deque



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







  return input(__UpperCamelCase					).strip().split(''' '''					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A		     =					{}
  for i in range(__UpperCamelCase					):
    __A		     =					[]

  for e in range(__UpperCamelCase					):
    __A     ,       __A     ,       __A		     =					(int(__UpperCamelCase					) 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_								=	(int(i) for i in _input('Number of nodes and edges: '))

       lowercase_								=	int(
           _input(
               'Press 1 or 2 or 3 \n'
               '1. Unweighted directed \n'
               '2. Unweighted undirected \n'
               '3. Weighted undirected \n'
           )[0]
       )

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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







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



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A     ,       __A		     =					{s}, deque([s]					)
  print(__UpperCamelCase					)
  while q:
    __A		     =					q.popleft()
    for v in g[u]:
      if v not in vis:
        vis.add(__UpperCamelCase					)
        q.append(__UpperCamelCase					)
        print(__UpperCamelCase					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A     ,       __A     ,       __A		     =					{s: 0}, set(), {s: 0}
  while True:
    if len(__UpperCamelCase					) == len(__UpperCamelCase					) - 1:
      break
    __A		     =					1_0_0_0_0_0
    for i in dist:
      if i not in known and dist[i] < mini:
        __A		     =					dist[i]
        __A		     =					i
    known.add(__UpperCamelCase					)
    for v in g[u]:
      if v[0] not in known and dist[u] + v[1] < dist.get(v[0]						,			1_0_0_0_0_0					):
        __A		     =					dist[u] + v[1]
        __A		     =					u
  for i in dist:
    if i != s:
      print(dist[i]					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase=None						,			__UpperCamelCase=None					):




  """simple docstring"""







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



def    lowerCAmelCase							(       ):




  """simple docstring"""







  __A		     =					input().strip()
  __A		     =					[]
  for _ in range(__UpperCamelCase					):
    a.append(map(__UpperCamelCase						,			input().strip().split()					)					)
  return a, n



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







  ((__A)     ,       (__A))		     =					a_and_n
  __A		     =					list(__UpperCamelCase					)
  __A		     =					[[0] * n for i in range(__UpperCamelCase					)]
  for k in range(__UpperCamelCase					):
    for i in range(__UpperCamelCase					):
      for j in range(__UpperCamelCase					):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          __A		     =					dist[i][k] + dist[k][j]
          __A		     =					k
  print(__UpperCamelCase					)



def    lowerCAmelCase							(       __UpperCamelCase						,			__UpperCamelCase					):




  """simple docstring"""







  __A     ,       __A     ,       __A		     =					{s: 0}, set(), {s: 0}
  while True:
    if len(__UpperCamelCase					) == len(__UpperCamelCase					) - 1:
      break
    __A		     =					1_0_0_0_0_0
    for i in dist:
      if i not in known and dist[i] < mini:
        __A		     =					dist[i]
        __A		     =					i
    known.add(__UpperCamelCase					)
    for v in g[u]:
      if v[0] not in known and v[1] < dist.get(v[0]						,			1_0_0_0_0_0					):
        __A		     =					v[1]
        __A		     =					u
  return dist



def    lowerCAmelCase							(       ):




  """simple docstring"""







  __A     ,       __A		     =					map(__UpperCamelCase						,			input().split(''' '''					)					)
  __A		     =					[]
  for _ in range(__UpperCamelCase					):
    edges.append(map(__UpperCamelCase						,			input().split(''' '''					)					)					)
  return edges, n



def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







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





def    lowerCAmelCase							(       __UpperCamelCase					):




  """simple docstring"""







  __A		     =					[]
  for node in graph:
    if not graph[node]:
      isolated.append(__UpperCamelCase					)
  return isolated









'''simple docstring'''







from __future__ import annotations

import unittest

from transformers import AlbertConfig, is_tf_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_tf, slow

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


if is_tf_available():
		import tensorflow as tf

		from transformers import TF_MODEL_FOR_PRETRAINING_MAPPING
		from transformers.models.albert.modeling_tf_albert import (
		    TF_ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
		    TFAlbertForMaskedLM,
		    TFAlbertForMultipleChoice,
		    TFAlbertForPreTraining,
		    TFAlbertForQuestionAnswering,
		    TFAlbertForSequenceClassification,
		    TFAlbertForTokenClassification,
		    TFAlbertModel,
		)

class      lowerCamelCase__     :






	'''simple docstring'''

	def __init__(  self		:  List[str]   ,		__A		:  Dict   ,		__A		:  Optional[Any]=13   ,		__A		:  Dict=7   ,		__A		:  Dict=True   ,		__A		:  Any=True   ,		__A		:  Any=True   ,		__A		:  List[str]=True   ,		__A		:  Union[str, Any]=99   ,		__A		:  Optional[int]=16   ,		__A		:  Tuple=32   ,		__A		:  Optional[int]=2   ,		__A		:  Dict=4   ,		__A		:  Dict=37   ,		__A		:  Any="gelu"   ,		__A		:  Union[str, Any]=0.1   ,		__A		:  List[str]=0.1   ,		__A		:  Any=512   ,		__A		:  Optional[Any]=16   ,		__A		:  List[str]=2   ,		__A		:  List[str]=0.0_2   ,		__A		:  List[str]=3   ,		__A		:  Dict=4   ,		__A		:  List[str]=None   ,		)     ->			int:




								'''simple docstring'''





								lowerCAmelCase__  =   parent
								lowerCAmelCase__  =   13
								lowerCAmelCase__  =   7
								lowerCAmelCase__  =   True
								lowerCAmelCase__  =   True
								lowerCAmelCase__  =   True
								lowerCAmelCase__  =   True
								lowerCAmelCase__  =   99
								lowerCAmelCase__  =   16
								lowerCAmelCase__  =   32
								lowerCAmelCase__  =   2
								lowerCAmelCase__  =   4
								lowerCAmelCase__  =   37
								lowerCAmelCase__  =   """gelu"""
								lowerCAmelCase__  =   0.1
								lowerCAmelCase__  =   0.1
								lowerCAmelCase__  =   512
								lowerCAmelCase__  =   16
								lowerCAmelCase__  =   2
								lowerCAmelCase__  =   0.0_2
								lowerCAmelCase__  =   3
								lowerCAmelCase__  =   4
								lowerCAmelCase__  =   None




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




								'''simple docstring'''





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

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

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

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

								lowerCAmelCase__  =   AlbertConfig(
								    vocab_size=self.vocab_size   ,		hidden_size=self.hidden_size   ,		embedding_size=self.embedding_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   ,		initializer_range=self.initializer_range   ,		)

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




	def      lowercase__							(  self		:  Optional[Any]   ,		__A		:  Optional[Any]   ,		__A		:  Tuple   ,		__A		:  List[Any]   ,		__A		:  Tuple   ,		__A		:  Dict   ,		__A		:  Optional[int]   ,		__A		:  List[Any]					)     ->			Optional[int]:




								'''simple docstring'''





								lowerCAmelCase__  =   TFAlbertModel(config=__A					)
								# inputs = {'input_ids': input_ids,
								#           'attention_mask': input_mask,
								#           'token_type_ids': token_type_ids}
								# sequence_output, pooled_output = model(**inputs)
								lowerCAmelCase__  =   {"""input_ids""": input_ids, """attention_mask""": input_mask, """token_type_ids""": token_type_ids}
								lowerCAmelCase__  =   model(__A					)

								lowerCAmelCase__  =   [input_ids, input_mask]
								lowerCAmelCase__  =   model(__A					)

								lowerCAmelCase__  =   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      lowercase__							(  self		:  List[str]   ,		__A		:  Optional[int]   ,		__A		:  Any   ,		__A		:  List[str]   ,		__A		:  Optional[int]   ,		__A		:  List[Any]   ,		__A		:  Optional[int]   ,		__A		:  Union[str, Any]					)     ->			Any:




								'''simple docstring'''





								lowerCAmelCase__  =   self.num_labels
								lowerCAmelCase__  =   TFAlbertForPreTraining(config=__A					)
								lowerCAmelCase__  =   {"""input_ids""": input_ids, """attention_mask""": input_mask, """token_type_ids""": token_type_ids}
								lowerCAmelCase__  =   model(__A					)
								self.parent.assertEqual(result.prediction_logits.shape   ,		(self.batch_size, self.seq_length, self.vocab_size)					)
								self.parent.assertEqual(result.sop_logits.shape   ,		(self.batch_size, self.num_labels)					)




	def      lowercase__							(  self		:  str   ,		__A		:  Dict   ,		__A		:  Any   ,		__A		:  List[Any]   ,		__A		:  Tuple   ,		__A		:  Union[str, Any]   ,		__A		:  int   ,		__A		:  str					)     ->			str:




								'''simple docstring'''





								lowerCAmelCase__  =   TFAlbertForMaskedLM(config=__A					)
								lowerCAmelCase__  =   {"""input_ids""": input_ids, """attention_mask""": input_mask, """token_type_ids""": token_type_ids}
								lowerCAmelCase__  =   model(__A					)
								self.parent.assertEqual(result.logits.shape   ,		(self.batch_size, self.seq_length, self.vocab_size)					)




	def      lowercase__							(  self		:  Dict   ,		__A		:  List[Any]   ,		__A		:  Union[str, Any]   ,		__A		:  Union[str, Any]   ,		__A		:  Optional[Any]   ,		__A		:  Optional[Any]   ,		__A		:  str   ,		__A		:  List[str]					)     ->			List[Any]:




								'''simple docstring'''





								lowerCAmelCase__  =   self.num_labels
								lowerCAmelCase__  =   TFAlbertForSequenceClassification(config=__A					)
								lowerCAmelCase__  =   {"""input_ids""": input_ids, """attention_mask""": input_mask, """token_type_ids""": token_type_ids}
								lowerCAmelCase__  =   model(__A					)
								self.parent.assertEqual(result.logits.shape   ,		(self.batch_size, self.num_labels)					)




	def      lowercase__							(  self		:  Dict   ,		__A		:  Any   ,		__A		:  Tuple   ,		__A		:  Union[str, Any]   ,		__A		:  List[Any]   ,		__A		:  List[Any]   ,		__A		:  Any   ,		__A		:  Any					)     ->			Dict:




								'''simple docstring'''





								lowerCAmelCase__  =   TFAlbertForQuestionAnswering(config=__A					)
								lowerCAmelCase__  =   {"""input_ids""": input_ids, """attention_mask""": input_mask, """token_type_ids""": token_type_ids}
								lowerCAmelCase__  =   model(__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      lowercase__							(  self		:  List[Any]   ,		__A		:  Union[str, Any]   ,		__A		:  List[Any]   ,		__A		:  Tuple   ,		__A		:  Dict   ,		__A		:  Tuple   ,		__A		:  List[str]   ,		__A		:  Dict					)     ->			List[Any]:




								'''simple docstring'''





								lowerCAmelCase__  =   self.num_choices
								lowerCAmelCase__  =   TFAlbertForMultipleChoice(config=__A					)
								lowerCAmelCase__  =   tf.tile(tf.expand_dims(__A   ,		1					)   ,		(1, self.num_choices, 1)					)
								lowerCAmelCase__  =   tf.tile(tf.expand_dims(__A   ,		1					)   ,		(1, self.num_choices, 1)					)
								lowerCAmelCase__  =   tf.tile(tf.expand_dims(__A   ,		1					)   ,		(1, self.num_choices, 1)					)
								lowerCAmelCase__  =   {
								    """input_ids""": multiple_choice_inputs_ids,
								    """attention_mask""": multiple_choice_input_mask,
								    """token_type_ids""": multiple_choice_token_type_ids,
								}
								lowerCAmelCase__  =   model(__A					)
								self.parent.assertListEqual(list(result["""logits"""].shape					)   ,		[self.batch_size, self.num_choices]					)




	def      lowercase__							(  self		:  int   ,		__A		:  Tuple   ,		__A		:  Optional[Any]   ,		__A		:  Any   ,		__A		:  Union[str, Any]   ,		__A		:  Tuple   ,		__A		:  str   ,		__A		:  Optional[Any]					)     ->			str:




								'''simple docstring'''





								lowerCAmelCase__  =   self.num_labels
								lowerCAmelCase__  =   TFAlbertForTokenClassification(config=__A					)
								lowerCAmelCase__  =   {
								    """input_ids""": input_ids,
								    """attention_mask""": input_mask,
								    """token_type_ids""": token_type_ids,
								}
								lowerCAmelCase__  =   model(__A					)
								self.parent.assertListEqual(list(result["""logits"""].shape					)   ,		[self.batch_size, self.seq_length, self.num_labels]					)




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




								'''simple docstring'''





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





@require_tf
class      lowerCamelCase__     (     _A,     _A,     unittest.TestCase				):






	'''simple docstring'''

	A__		=	(
	    (
	        TFAlbertModel,
	        TFAlbertForPreTraining,
	        TFAlbertForMaskedLM,
	        TFAlbertForSequenceClassification,
	        TFAlbertForQuestionAnswering,
	        TFAlbertForTokenClassification,
	        TFAlbertForMultipleChoice,
	    )
	    if is_tf_available()
	    else ()
	)
	A__		=	(
	    {
	        '''feature-extraction''': TFAlbertModel,
	        '''fill-mask''': TFAlbertForMaskedLM,
	        '''question-answering''': TFAlbertForQuestionAnswering,
	        '''text-classification''': TFAlbertForSequenceClassification,
	        '''token-classification''': TFAlbertForTokenClassification,
	        '''zero-shot''': TFAlbertForSequenceClassification,
	    }
	    if is_tf_available()
	    else {}
	)
	A__		=	False
	A__		=	False




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




								'''simple docstring'''





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

								if return_labels:
															if model_class in get_values(__A					):
																						lowerCAmelCase__  =   tf.zeros(self.model_tester.batch_size   ,		dtype=tf.intaa					)

								return inputs_dict




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




								'''simple docstring'''





								lowerCAmelCase__  =   TFAlbertModelTester(self					)
								lowerCAmelCase__  =   ConfigTester(self   ,		config_class=__A   ,		hidden_size=37					)




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




								'''simple docstring'''





								self.config_tester.run_common_tests()




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




								'''simple docstring'''





								lowerCAmelCase__  =   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_albert_model(*__A					)




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




								'''simple docstring'''





								lowerCAmelCase__  =   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_albert_for_pretraining(*__A					)




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




								'''simple docstring'''





								lowerCAmelCase__  =   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_albert_for_masked_lm(*__A					)




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




								'''simple docstring'''





								lowerCAmelCase__  =   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_albert_for_multiple_choice(*__A					)




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




								'''simple docstring'''





								lowerCAmelCase__  =   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_albert_for_sequence_classification(*__A					)




	def      lowercase__							(  self		:  Any					)     ->			Any:




								'''simple docstring'''





								lowerCAmelCase__  =   self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_albert_for_question_answering(*__A					)




	@slow
	def      lowercase__							(  self		:  Tuple					)     ->			Dict:




								'''simple docstring'''





								for model_name in TF_ALBERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															lowerCAmelCase__  =   TFAlbertModel.from_pretrained(__A					)
															self.assertIsNotNone(__A					)





@require_tf
class      lowerCamelCase__     (     unittest.TestCase				):






	'''simple docstring'''

	@slow
	def      lowercase__							(  self		:  Optional[int]					)     ->			str:




								'''simple docstring'''





								lowerCAmelCase__  =   TFAlbertForPreTraining.from_pretrained("""albert-base-v2"""					)
								lowerCAmelCase__  =   tf.constant([[0, 1, 2, 3, 4, 5]]					)
								lowerCAmelCase__  =   model(__A					)[0]

								lowerCAmelCase__  =   [1, 6, 3_0000]
								self.assertEqual(output.shape   ,		__A					)

								lowerCAmelCase__  =   tf.constant(
								    [
								        [
								            [4.5_9_5_6_6_8, 0.7_4_4_6_2_7_5_4, -1.8_1_8_1_4_7],
								            [4.5_9_5_4_3_4_7, 0.7_4_5_4_1_8_4, -1.8_1_8_8_2_5_8],
								            [4.5_9_5_4_9_0_5, 0.7_4_4_8_2_3_5, -1.8_1_8_2_3_1_6],
								        ]
								    ]					)
								tf.debugging.assert_near(output[:, :3, :3]   ,		__A   ,		atol=1E-4					)





