






import unittest

from transformers import ErnieMConfig, is_torch_available
from transformers.testing_utils import 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 (
		    ErnieMForInformationExtraction,
		    ErnieMForMultipleChoice,
		    ErnieMForQuestionAnswering,
		    ErnieMForSequenceClassification,
		    ErnieMForTokenClassification,
		    ErnieMModel,
		)
		from transformers.models.ernie_m.modeling_ernie_m import ERNIE_M_PRETRAINED_MODEL_ARCHIVE_LIST



class  __UpperCAmelCase						:







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







									'''simple docstring'''




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







			def 				UpperCamelCase (      self:    List[str]	):







									'''simple docstring'''




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

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

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

									_SCREAMING_SNAKE_CASE       =    self.get_config()

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







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




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

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

									return config, input_ids, input_mask







			def 				UpperCamelCase (      self:    List[str]	):







									'''simple docstring'''




									return ErnieMConfig(
									    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 ,      initializer_range=self.initializer_range ,      )







			def 				UpperCamelCase (      self:    Optional[Any] ,      UpperCAmelCase_:    Any ,      UpperCAmelCase_:    Union[str, Any] ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    int	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    ErnieMModel(config=UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()
									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_ ,      return_dict=UpperCAmelCase_	)
									self.parent.assertEqual(result.last_hidden_state.shape ,      (self.batch_size, self.seq_length, self.hidden_size)	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    Any ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    ErnieMForQuestionAnswering(config=UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()
									_SCREAMING_SNAKE_CASE       =    model(
									    UpperCAmelCase_ ,      attention_mask=UpperCAmelCase_ ,      start_positions=UpperCAmelCase_ ,      end_positions=UpperCAmelCase_ ,      )
									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 				UpperCamelCase (      self:    Optional[Any] ,      UpperCAmelCase_:    Union[str, Any] ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    Dict ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    List[str]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    ErnieMForInformationExtraction(config=UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()
									_SCREAMING_SNAKE_CASE       =    torch.ones_like(UpperCAmelCase_ ,      dtype=torch.floataa	)
									_SCREAMING_SNAKE_CASE       =    model(
									    UpperCAmelCase_ ,      attention_mask=UpperCAmelCase_ ,      start_positions=UpperCAmelCase_ ,      end_positions=UpperCAmelCase_ ,      )
									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 				UpperCamelCase (      self:    Any ,      UpperCAmelCase_:    Dict ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.num_labels
									_SCREAMING_SNAKE_CASE       =    ErnieMForSequenceClassification(UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()
									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_ ,      attention_mask=UpperCAmelCase_ ,      labels=UpperCAmelCase_	)
									self.parent.assertEqual(result.logits.shape ,      (self.batch_size, self.num_labels)	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    Tuple ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    Dict ,      UpperCAmelCase_:    Optional[int] ,      UpperCAmelCase_:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.num_labels
									_SCREAMING_SNAKE_CASE       =    ErnieMForTokenClassification(config=UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()
									input_ids.to(UpperCAmelCase_	)
									input_mask.to(UpperCAmelCase_	)
									token_labels.to(UpperCAmelCase_	)

									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_ ,      attention_mask=UpperCAmelCase_ ,      labels=UpperCAmelCase_	)

									self.parent.assertEqual(result.logits.shape ,      (self.batch_size, self.seq_length, self.num_labels)	)







			def 				UpperCamelCase (      self:    Dict ,      UpperCAmelCase_:    List[Any] ,      UpperCAmelCase_:    Any ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    Tuple ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.num_choices
									_SCREAMING_SNAKE_CASE       =    ErnieMForMultipleChoice(config=UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()
									_SCREAMING_SNAKE_CASE       =    input_ids.unsqueeze(1	).expand(-1 ,      self.num_choices ,      -1	).contiguous()
									_SCREAMING_SNAKE_CASE       =    input_mask.unsqueeze(1	).expand(-1 ,      self.num_choices ,      -1	).contiguous()
									_SCREAMING_SNAKE_CASE       =    model(
									    UpperCAmelCase_ ,      attention_mask=UpperCAmelCase_ ,      labels=UpperCAmelCase_ ,      )
									self.parent.assertEqual(result.logits.shape ,      (self.batch_size, self.num_choices)	)







			def 				UpperCamelCase (      self:    Any	):







									'''simple docstring'''




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



@require_torch
class  __UpperCAmelCase						(_UpperCAmelCase			,_UpperCAmelCase			,unittest.TestCase       ):
			__snake_case							: Any							=				(
			    (
			        ErnieMModel,
			        ErnieMForMultipleChoice,
			        ErnieMForQuestionAnswering,
			        ErnieMForSequenceClassification,
			        ErnieMForTokenClassification,
			    )
			    if is_torch_available()
			    else ()
			)
			__snake_case							: Any							=				()
			__snake_case							: Dict							=				(
			    {
			        "feature-extraction": ErnieMModel,
			        "question-answering": ErnieMForQuestionAnswering,
			        "text-classification": ErnieMForSequenceClassification,
			        "token-classification": ErnieMForTokenClassification,
			        "zero-shot": ErnieMForSequenceClassification,
			    }
			    if is_torch_available()
			    else {}
			)
			__snake_case							: Any							=				False







			def 				UpperCamelCase (      self:    Dict ,      UpperCAmelCase_:    Any ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    Dict ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    Tuple	):







									'''simple docstring'''




									if pipeline_test_casse_name == "QAPipelineTests":
															return True

									return False







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    ErnieMModelTester(self	)
									_SCREAMING_SNAKE_CASE       =    ConfigTester(self ,      config_class=UpperCAmelCase_ ,      hidden_size=37	)







			def 				UpperCamelCase (      self:    List[str]	):







									'''simple docstring'''




									self.config_tester.run_common_tests()







			def 				UpperCamelCase (      self:    Tuple	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_model(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Dict	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									for type in ["absolute", "relative_key", "relative_key_query"]:
															_SCREAMING_SNAKE_CASE       =    type
															self.model_tester.create_and_check_model(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    int	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_multiple_choice(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Optional[Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_question_answering(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    int	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_sequence_classification(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_information_extraction(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_token_classification(*UpperCAmelCase_	)







			@slow
			def 				UpperCamelCase (      self:    int	):







									'''simple docstring'''




									for model_name in ERNIE_M_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															_SCREAMING_SNAKE_CASE       =    ErnieMModel.from_pretrained(UpperCAmelCase_	)
															self.assertIsNotNone(UpperCAmelCase_	)



@require_torch
class  __UpperCAmelCase						(unittest.TestCase       ):







			@slow
			def 				UpperCamelCase (      self:    Optional[Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    ErnieMModel.from_pretrained("""susnato/ernie-m-base_pytorch"""	)
									model.eval()
									_SCREAMING_SNAKE_CASE       =    torch.tensor([[0, 1, 2, 3, 4, 5]]	)
									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_	)[0]

									# TODO Replace vocab size
									_SCREAMING_SNAKE_CASE       =    768

									_SCREAMING_SNAKE_CASE       =    torch.Size((1, 6, hidden_size)	)
									self.assertEqual(output.shape ,      UpperCAmelCase_	)

									_SCREAMING_SNAKE_CASE       =    torch.tensor(
									    [[[-0.00_12, 0.12_45, -0.02_14], [-0.07_42, 0.02_44, -0.07_71], [-0.03_33, 0.11_64, -0.15_54]]]	)

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









import math
import sys



class  __UpperCAmelCase						:







			def __init__(      self:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    []
									_SCREAMING_SNAKE_CASE       =    {}  # To store the pos of node in array







			def 				UpperCamelCase (      self:    List[str]	):







									'''simple docstring'''




									return self.cur_size == 0







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.left(UpperCAmelCase_	)
									_SCREAMING_SNAKE_CASE       =    self.right(UpperCAmelCase_	)
									if lc < self.cur_size and self.array(UpperCAmelCase_	)[0] < self.array(UpperCAmelCase_	)[0]:
															_SCREAMING_SNAKE_CASE       =    lc
									else:
															_SCREAMING_SNAKE_CASE       =    idx
									if rc < self.cur_size and self.array(UpperCAmelCase_	)[0] < self.array(UpperCAmelCase_	)[0]:
															_SCREAMING_SNAKE_CASE       =    rc
									if smallest != idx:
															self.swap(UpperCAmelCase_ ,      UpperCAmelCase_	)
															self.min_heapify(UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Tuple	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.cur_size
									self.cur_size += 1
									self.array.append((sys.maxsize, tup[1])	)
									self.decrease_key((sys.maxsize, tup[1]) ,      tup[0]	)







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.array[0][1]
									_SCREAMING_SNAKE_CASE       =    self.array[self.cur_size - 1]
									self.cur_size -= 1
									self.min_heapify(1	)
									del self.pos[min_node]
									return min_node







			def 				UpperCamelCase (      self:    Dict ,      UpperCAmelCase_:    List[Any]	):







									'''simple docstring'''




									return 2 * i + 1







			def 				UpperCamelCase (      self:    Optional[Any] ,      UpperCAmelCase_:    List[Any]	):







									'''simple docstring'''




									return 2 * i + 2







			def 				UpperCamelCase (      self:    Union[str, Any] ,      UpperCAmelCase_:    int	):







									'''simple docstring'''




									return math.floor(i / 2	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    j
									_SCREAMING_SNAKE_CASE       =    i
									_SCREAMING_SNAKE_CASE       =    self.array[i]
									_SCREAMING_SNAKE_CASE       =    self.array[j]
									_SCREAMING_SNAKE_CASE       =    temp







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Dict ,      UpperCAmelCase_:    Dict	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.pos[tup[1]]
									# assuming the new_d is atmost old_d
									_SCREAMING_SNAKE_CASE       =    (new_d, tup[1])
									while idx > 0 and self.array[self.par(UpperCAmelCase_	)][0] > self.array[idx][0]:
															self.swap(UpperCAmelCase_ ,      self.par(UpperCAmelCase_	)	)
															_SCREAMING_SNAKE_CASE       =    self.par(UpperCAmelCase_	)



class  __UpperCAmelCase						:







			def __init__(      self:    Tuple ,      UpperCAmelCase_:    Any	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    {}  # To store graph: u -> (v,w)
									_SCREAMING_SNAKE_CASE       =    num  # Number of nodes in graph
									# To store the distance from source vertex
									_SCREAMING_SNAKE_CASE       =    [0] * self.num_nodes
									_SCREAMING_SNAKE_CASE       =    [-1] * self.num_nodes  # To store the path







			def 				UpperCamelCase (      self:    Tuple ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    List[Any] ,      UpperCAmelCase_:    Any	):







									'''simple docstring'''




									if u in self.adjList:
															self.adjList[u].append((v, w)	)
									else:
															_SCREAMING_SNAKE_CASE       =    [(v, w)]

									# Assuming undirected graph
									if v in self.adjList:
															self.adjList[v].append((u, w)	)
									else:
															_SCREAMING_SNAKE_CASE       =    [(u, w)]







			def 				UpperCamelCase (      self:    Dict	):







									'''simple docstring'''




									for u in self.adjList:
															print(UpperCAmelCase_ ,      """->""" ,      """ -> """.join(str(F'{v}({w})'	) for v, w in self.adjList[u]	)	)







			def 				UpperCamelCase (      self:    Optional[int] ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    [-1] * self.num_nodes
									# src is the source node
									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    PriorityQueue()
									q.insert((0, src)	)  # (dist from src, node)
									for u in self.adjList:
															if u != src:
																					_SCREAMING_SNAKE_CASE       =    sys.maxsize  # Infinity
																					_SCREAMING_SNAKE_CASE       =    -1

									while not q.is_empty():
															_SCREAMING_SNAKE_CASE       =    q.extract_min()  # Returns node with the min dist from source
															# Update the distance of all the neighbours of u and
															# if their prev dist was INFINITY then push them in Q
															for v, w in self.adjList[u]:
																					_SCREAMING_SNAKE_CASE       =    self.dist[u] + w
																					if self.dist[v] > new_dist:
																											if self.dist[v] == sys.maxsize:
																																	q.insert((new_dist, v)	)
																											else:
																																	q.decrease_key((self.dist[v], v) ,      UpperCAmelCase_	)
																											_SCREAMING_SNAKE_CASE       =    new_dist
																											_SCREAMING_SNAKE_CASE       =    u

        # Show the shortest distances from src
									self.show_distances(UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Optional[int] ,      UpperCAmelCase_:    int	):







									'''simple docstring'''




									print(F'Distance from node: {src}'	)
									for u in range(self.num_nodes	):
															print(F'Node {u} has distance: {self.dist[u]}'	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    List[str]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    []
									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    dest
									# Backtracking from dest to src
									while self.par[temp] != -1:
															path.append(UpperCAmelCase_	)
															if temp != src:
																					for v, w in self.adjList[temp]:
																											if v == self.par[temp]:
																																	cost += w
																																	break
															_SCREAMING_SNAKE_CASE       =    self.par[temp]
									path.append(UpperCAmelCase_	)
									path.reverse()

									print(F'----Path to reach {dest} from {src}----'	)
									for u in path:
															print(F'{u}' ,      end=""" """	)
															if u != dest:
																					print("""-> """ ,      end=""""""	)

									print("""\nTotal cost of path: """ ,      UpperCAmelCase_	)


if __name__ == "__main__":
		UpperCamelCase												=      Graph(9)
		graph.add_edge(0, 1, 4)
		graph.add_edge(0, 7, 8)
		graph.add_edge(1, 2, 8)
		graph.add_edge(1, 7, 11)
		graph.add_edge(2, 3, 7)
		graph.add_edge(2, 8, 2)
		graph.add_edge(2, 5, 4)
		graph.add_edge(3, 4, 9)
		graph.add_edge(3, 5, 14)
		graph.add_edge(4, 5, 10)
		graph.add_edge(5, 6, 2)
		graph.add_edge(6, 7, 1)
		graph.add_edge(6, 8, 6)
		graph.add_edge(7, 8, 7)
		graph.show_graph()
		graph.dijkstra(0)
		graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21

