


"""simple docstring"""
import math
import sys





class   __A  :





							'''simple docstring'''

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



														"""simple docstring"""



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



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



														"""simple docstring"""



														return self.cur_size == 0



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



														"""simple docstring"""



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



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



														"""simple docstring"""



														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 		lowerCAmelCase							(					self				:   Optional[Any]							)       ->str:



														"""simple docstring"""



														snake_case_     							=		self.array[0][1]
														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 		lowerCAmelCase							(					self				:   List[str]		,							UpperCAmelCase_				:   str							)       ->Any:



														"""simple docstring"""



														return 2 * i + 1



							def 		lowerCAmelCase							(					self				:   str		,							UpperCAmelCase_				:   Dict							)       ->Tuple:



														"""simple docstring"""



														return 2 * i + 2



							def 		lowerCAmelCase							(					self				:   List[Any]		,							UpperCAmelCase_				:   Optional[Any]							)       ->int:



														"""simple docstring"""



														return math.floor(i / 2							)



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



														"""simple docstring"""



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



							def 		lowerCAmelCase							(					self				:   List[Any]		,							UpperCAmelCase_				:   int		,							UpperCAmelCase_				:   Tuple							)       ->str:



														"""simple docstring"""



														snake_case_     							=		self.pos[tup[1]]
														# assuming the new_d is atmost old_d
														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_							)							)
																					snake_case_     							=		self.par(UpperCAmelCase_							)





class   __A  :





							'''simple docstring'''

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



														"""simple docstring"""



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



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



														"""simple docstring"""



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

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



							def 		lowerCAmelCase							(					self				:   str							)       ->int:



														"""simple docstring"""



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



							def 		lowerCAmelCase							(					self				:   Optional[int]		,							UpperCAmelCase_				:   Union[str, Any]							)       ->Optional[Any]:



														"""simple docstring"""



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

														while not q.is_empty():
																					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]:
																												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_							)
																																			snake_case_     							=		new_dist
																																			snake_case_     							=		u

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



							def 		lowerCAmelCase							(					self				:   Optional[Any]		,							UpperCAmelCase_				:   Optional[int]							)       ->Any:



														"""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 		lowerCAmelCase							(					self				:   Any		,							UpperCAmelCase_				:   int		,							UpperCAmelCase_				:   str							)       ->Tuple:



														"""simple docstring"""



														snake_case_     							=		[]
														snake_case_     							=		0
														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
																					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__":
				__SCREAMING_SNAKE_CASE				:     Union[str, Any]		=     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 argparse
import json
import re
import string
import sys
from collections import Counter







def     _a					(   _SCREAMING_SNAKE_CASE					)     ->					Any:

							def remove_articles(_SCREAMING_SNAKE_CASE					):
														return re.sub(r"""\b(a|an|the)\b"""					,			""" """					,			_SCREAMING_SNAKE_CASE					)

							def white_space_fix(_SCREAMING_SNAKE_CASE					):
														return " ".join(text.split()					)

							def remove_punc(_SCREAMING_SNAKE_CASE					):
														snake_case_     							=		set(string.punctuation					)
														return "".join(ch for ch in text if ch not in exclude					)

							def lower(_SCREAMING_SNAKE_CASE					):
														return text.lower()

							return white_space_fix(remove_articles(remove_punc(lower(_SCREAMING_SNAKE_CASE					)					)					)					)







def     _a					(   _SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					)     ->					Optional[int]:
							snake_case_     							=		normalize_answer(_SCREAMING_SNAKE_CASE					).split()
							snake_case_     							=		normalize_answer(_SCREAMING_SNAKE_CASE					).split()
							snake_case_     							=		Counter(_SCREAMING_SNAKE_CASE					) & Counter(_SCREAMING_SNAKE_CASE					)
							snake_case_     							=		sum(common.values()					)
							if num_same == 0:
														return 0
							snake_case_     							=		1.0 * num_same / len(_SCREAMING_SNAKE_CASE					)
							snake_case_     							=		1.0 * num_same / len(_SCREAMING_SNAKE_CASE					)
							snake_case_     							=		(2 * precision * recall) / (precision + recall)
							return fa







def     _a					(   _SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					)     ->					Union[str, Any]:
							return normalize_answer(_SCREAMING_SNAKE_CASE					) == normalize_answer(_SCREAMING_SNAKE_CASE					)







def     _a					(   _SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					)     ->					Optional[int]:
							snake_case_     							=		[]
							for ground_truth in ground_truths:
														snake_case_     							=		metric_fn(_SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					)
														scores_for_ground_truths.append(_SCREAMING_SNAKE_CASE					)
							return max(_SCREAMING_SNAKE_CASE					)







def     _a					(   _SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					)     ->					Optional[int]:
							snake_case_     							=		snake_case_     							=		snake_case_     							=		0
							for article in dataset:
														for paragraph in article["paragraphs"]:
																					for qa in paragraph["qas"]:
																												total += 1
																												if qa["id"] not in predictions:
																																			snake_case_     							=		"""Unanswered question """ + qa["""id"""] + """ will receive score 0."""
																																			print(_SCREAMING_SNAKE_CASE					,			file=sys.stderr					)
																																			continue
																												snake_case_     							=		[x["""text"""] for x in qa["""answers"""]]
																												snake_case_     							=		predictions[qa["""id"""]]
																												exact_match += metric_max_over_ground_truths(_SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					)
																												fa += metric_max_over_ground_truths(_SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					,			_SCREAMING_SNAKE_CASE					)

							snake_case_     							=		100.0 * exact_match / total
							snake_case_     							=		100.0 * fa / total

							return {"exact_match": exact_match, "f1": fa}


if __name__ == "__main__":
				__SCREAMING_SNAKE_CASE				:     Tuple		=     '1.1'
				__SCREAMING_SNAKE_CASE				:     Union[str, Any]		=     argparse.ArgumentParser(description='Evaluation for SQuAD ' + expected_version)
				parser.add_argument('dataset_file', help='Dataset file')
				parser.add_argument('prediction_file', help='Prediction File')
				__SCREAMING_SNAKE_CASE				:     Union[str, Any]		=     parser.parse_args()
				with open(args.dataset_file) as dataset_file:
								__SCREAMING_SNAKE_CASE				:     Optional[Any]		=     json.load(dataset_file)
								if dataset_json["version"] != expected_version:
												print(
												    'Evaluation expects v-' + expected_version + ', but got dataset with v-' + dataset_json['version'],
												    file=sys.stderr,
												)
								__SCREAMING_SNAKE_CASE				:     str		=     dataset_json['data']
				with open(args.prediction_file) as prediction_file:
								__SCREAMING_SNAKE_CASE				:     int		=     json.load(prediction_file)
				print(json.dumps(evaluate(dataset, predictions)))



