





import math
import sys
class SCREAMING_SNAKE_CASE_    :






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







							"""simple docstring"""


							snake_case_		:      Dict           =						0
							snake_case_		:      List[Any]           =						[]
							snake_case_		:      Optional[int]           =						{}  # To store the pos of node in array






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







							"""simple docstring"""


							return self.cur_size == 0






						def UpperCAmelCase_					(   self   :   int		, _A   :   Tuple						)				->     Optional[int]:







							"""simple docstring"""


							snake_case_		:      str           =						self.left(_A						)
							snake_case_		:      Dict           =						self.right(_A						)
							if lc < self.cur_size and self.array(_A						)[0] < self.array(_A						)[0]:
								snake_case_		:      Tuple           =						lc
							else:
								snake_case_		:      int           =						idx
							if rc < self.cur_size and self.array(_A						)[0] < self.array(_A						)[0]:
								snake_case_		:      Optional[Any]           =						rc
							if smallest != idx:
								self.swap(_A		, _A						)
								self.min_heapify(_A						)






						def UpperCAmelCase_					(   self   :   Any		, _A   :   List[str]						)				->     Dict:







							"""simple docstring"""


							snake_case_		:      Any           =						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   :   Optional[int]						)				->     Optional[Any]:







							"""simple docstring"""


							snake_case_		:      str           =						self.array[0][1]
							snake_case_		:      Union[str, Any]           =						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		, _A   :   Any						)				->     int:







							"""simple docstring"""


							return 2 * i + 1






						def UpperCAmelCase_					(   self   :   List[str]		, _A   :   Dict						)				->     Optional[Any]:







							"""simple docstring"""


							return 2 * i + 2






						def UpperCAmelCase_					(   self   :   List[str]		, _A   :   Optional[Any]						)				->     Any:







							"""simple docstring"""


							return math.floor(i / 2						)






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







							"""simple docstring"""


							snake_case_		:      Optional[int]           =						j
							snake_case_		:      Optional[int]           =						i
							snake_case_		:      Optional[Any]           =						self.array[i]
							snake_case_		:      List[Any]           =						self.array[j]
							snake_case_		:      Tuple           =						temp






						def UpperCAmelCase_					(   self   :   str		, _A   :   Optional[int]		, _A   :   Dict						)				->     int:







							"""simple docstring"""


							snake_case_		:      List[Any]           =						self.pos[tup[1]]
							# assuming the new_d is atmost old_d
							snake_case_		:      Optional[Any]           =						(new_d, tup[1])
							while idx > 0 and self.array[self.par(_A						)][0] > self.array[idx][0]:
								self.swap(_A		, self.par(_A						)						)
								snake_case_		:      List[Any]           =						self.par(_A						)
class SCREAMING_SNAKE_CASE_    :






						def __init__(   self   :   Dict		, _A   :   List[Any]						)				->     Any:







							"""simple docstring"""


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






						def UpperCAmelCase_					(   self   :   Any		, _A   :   List[str]		, _A   :   Dict		, _A   :   Tuple						)				->     Optional[Any]:







							"""simple docstring"""


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

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






						def UpperCAmelCase_					(   self   :   Tuple						)				->     Tuple:







							"""simple docstring"""


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






						def UpperCAmelCase_					(   self   :   Tuple		, _A   :   List[str]						)				->     List[str]:







							"""simple docstring"""


							snake_case_		:      Union[str, Any]           =						[-1] * self.num_nodes
							# src is the source node
							snake_case_		:      List[Any]           =						0
							snake_case_		:      Optional[Any]           =						PriorityQueue()
							q.insert((0, src)						)  # (dist from src, node)
							for u in self.adjList:
								if u != src:
									snake_case_		:      Tuple           =						sys.maxsize  # Infinity
									snake_case_		:      Optional[int]           =						-1

							while not q.is_empty():
								snake_case_		:      int           =						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]:
									snake_case_		:      Dict           =						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)		, _A						)
										snake_case_		:      int           =						new_dist
										snake_case_		:      Any           =						u

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






						def UpperCAmelCase_					(   self   :   List[Any]		, _A   :   int						)				->     Dict:







							"""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   :   Optional[int]		, _A   :   str		, _A   :   Dict						)				->     Optional[int]:







							"""simple docstring"""


							snake_case_		:      Dict           =						[]
							snake_case_		:      str           =						0
							snake_case_		:      List[Any]           =						dest
							# Backtracking from dest to src
							while self.par[temp] != -1:
								path.append(_A						)
								if temp != src:
									for v, w in self.adjList[temp]:
										if v == self.par[temp]:
											cost += w
											break
								snake_case_		:      List[Any]           =						self.par[temp]
							path.append(_A						)
							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: '		, _A						)


if __name__ == "__main__":
						_SCREAMING_SNAKE_CASE   						=		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





"""simple docstring"""






import re
import tempfile
import unittest
from pathlib import Path

from datasets.utils.metadata import DatasetMetadata




def        A_					(					UpperCAmelCase__				)     ->     str:
   a   :	Optional[int]						=    min(re.search('^ +'       ,   UpperCAmelCase__				).end() if t.startswith(' '				) else 0 for t in string.splitlines()				)
   return "\n".join([line[indent_level:] for line in string.splitlines() if indent_level < len(UpperCAmelCase__				)]				)


SCREAMING_SNAKE_CASE__				:  Union[str, Any]						= "\\n---\nlanguage:\n- zh\n- en\ntask_ids:\n- sentiment-classification\n---\n# Begin of markdown\n\nSome cool dataset card\n"

SCREAMING_SNAKE_CASE__				:  List[str]						= "\\n---\n---\n# Begin of markdown\n\nSome cool dataset card\n"


SCREAMING_SNAKE_CASE__				:  Dict						= "\\n# Begin of markdown\n\nSome cool dataset card\n"


class 	A_       (     unittest.TestCase   ):





  """simple docstring"""

  def 							lowercase_     (						self						)				->					Any:
     with tempfile.TemporaryDirectory() as tmp_dir:
        a   :	Optional[Any]						=    Path(__UpperCAmelCase						) / 'README.md'
        with open(__UpperCAmelCase  ,					'w+'						) as readme_file:
           readme_file.write(__UpperCAmelCase						)
        a   :	str						=    DatasetMetadata.from_readme(__UpperCAmelCase						)
        self.assertDictEqual(__UpperCAmelCase  ,					{'language': ['zh', 'en'], 'task_ids': ['sentiment-classification']}						)

        with open(__UpperCAmelCase  ,					'w+'						) as readme_file:
           readme_file.write(__UpperCAmelCase						)
        a   :	Optional[Any]						=    DatasetMetadata.from_readme(__UpperCAmelCase						)
        self.assertDictEqual(__UpperCAmelCase  ,					{}						)

        with open(__UpperCAmelCase  ,					'w+'						) as readme_file:
           readme_file.write(__UpperCAmelCase						)
        a   :	str						=    DatasetMetadata.from_readme(__UpperCAmelCase						)
        self.assertEqual(__UpperCAmelCase  ,					{}						)






  def 							lowercase_     (						self						)				->					Tuple:
     a   :	List[str]						=    _dedent(
         '\\n            annotations_creators:\n            - found\n            language_creators:\n            - found\n            language:\n            - en\n            license:\n            - unknown\n            multilinguality:\n            - monolingual\n            pretty_name: Test Dataset\n            size_categories:\n            - 10K<n<100K\n            source_datasets:\n            - extended|other-yahoo-webscope-l6\n            task_categories:\n            - question-answering\n            task_ids:\n            - open-domain-qa\n            '						)
     assert DatasetMetadata.from_yaml_string(__UpperCAmelCase						)

     a   :	Optional[Any]						=    _dedent(
         '\\n            annotations_creators:\n            - found\n            language:\n            - en\n            license:\n            - unknown\n            multilinguality:\n            - monolingual\n            pretty_name: Test Dataset\n            size_categories:\n            - 10K<n<100K\n            source_datasets:\n            - extended|other-yahoo-webscope-l6\n            task_categories:\n            - question-answering\n            task_ids:\n            - open-domain-qa\n            task_ids:\n            - open-domain-qa\n            '						)
     with self.assertRaises(__UpperCAmelCase						):
        DatasetMetadata.from_yaml_string(__UpperCAmelCase						)

     a   :	List[Any]						=    _dedent(
         '\\n            annotations_creators:\n            - found\n            language_creators:\n            - found\n            language:\n            - en\n            license:\n            - unknown\n            multilinguality:\n            - monolingual\n            pretty_name: Test Dataset\n            size_categories:\n            - 10K<n<100K\n            source_datasets:\n            - extended|other-yahoo-webscope-l6\n            task_categories:\n            - text-classification\n            task_ids:\n            - multi-class-classification\n            paperswithcode_id:\n            - squad\n            configs:\n            - en\n            train-eval-index:\n            - config: en\n              task: text-classification\n              task_id: multi_class_classification\n              splits:\n                train_split: train\n                eval_split: test\n              col_mapping:\n                text: text\n                label: target\n              metrics:\n                - type: accuracy\n                  name: Accuracy\n            extra_gated_prompt: |\n              By clicking on “Access repository” below, you also agree to ImageNet Terms of Access:\n              [RESEARCHER_FULLNAME] (the "Researcher") has requested permission to use the ImageNet database (the "Database") at Princeton University and Stanford University. In exchange for such permission, Researcher hereby agrees to the following terms and conditions:\n              1. Researcher shall use the Database only for non-commercial research and educational purposes.\n            extra_gated_fields:\n              Company: text\n              Country: text\n              I agree to use this model for non-commerical use ONLY: checkbox\n            '						)
     assert DatasetMetadata.from_yaml_string(__UpperCAmelCase						)





