




"""simple docstring"""




import argparse
import json
import re
import string
import sys
from collections import Counter







def       __UpperCAmelCase      (				__UpperCamelCase					):

			def remove_articles(__UpperCamelCase					):
						return re.sub(R'''\b(a|an|the)\b'''					,							''' '''					,							__UpperCamelCase					)

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

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

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

			return white_space_fix(remove_articles(remove_punc(lower(__UpperCamelCase					)					)					)					)







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					):
			__lowercase	:       Optional[int]				=   normalize_answer(__UpperCamelCase					).split()
			__lowercase	:       List[str]				=   normalize_answer(__UpperCamelCase					).split()
			__lowercase	:       List[Any]				=   Counter(__UpperCamelCase					) & Counter(__UpperCamelCase					)
			__lowercase	:       Tuple				=   sum(common.values()					)
			if num_same == 0:
						return 0
			__lowercase	:       str				=   1.0 * num_same / len(__UpperCamelCase					)
			__lowercase	:       List[str]				=   1.0 * num_same / len(__UpperCamelCase					)
			__lowercase	:       Optional[int]				=   (2 * precision * recall) / (precision + recall)
			return fa







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					):
			return normalize_answer(__UpperCamelCase					) == normalize_answer(__UpperCamelCase					)







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					):
			__lowercase	:       Any				=   []
			for ground_truth in ground_truths:
						__lowercase	:       Any				=   metric_fn(__UpperCamelCase					,							__UpperCamelCase					)
						scores_for_ground_truths.append(__UpperCamelCase					)
			return max(__UpperCamelCase					)







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					):
			__lowercase	:       Any				=   0
			__lowercase	:       List[Any]				=   []
			for passage in dataset:
						for qa in passage["qas"]:
									total += 1
									if qa["id"] not in predictions:
												__lowercase	:       List[str]				=   f"""Unanswered question {qa["id"]} will receive score 0."""
												print(__UpperCamelCase					,							file=sys.stderr					)
												continue

									__lowercase	:       List[Any]				=   [x['''text'''] for x in qa['''answers''']]
									__lowercase	:       Any				=   predictions[qa['''id''']]

									__lowercase	:       List[str]				=   metric_max_over_ground_truths(__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					)
									if int(_exact_match					) == 1:
												correct_ids.append(qa['''id''']					)
									exact_match += _exact_match

									fa += metric_max_over_ground_truths(__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					)

			__lowercase	:       Optional[int]				=   exact_match / total
			__lowercase	:       Tuple				=   fa / total

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


if __name__ == "__main__":
			a_            =   '1.0'
			a_            =   argparse.ArgumentParser('Official evaluation script for ReCoRD v1.0.')
			parser.add_argument('data_file', help='The dataset file in JSON format.')
			parser.add_argument('pred_file', help='The model prediction file in JSON format.')
			parser.add_argument('--output_correct_ids', action='store_true', help='Output the correctly answered query IDs.')
			a_            =   parser.parse_args()

			with open(args.data_file) as data_file:
						a_            =   json.load(data_file)
						if dataset_json["version"] != expected_version:
									print(
									    F"Evaluation expects v-{expected_version}, but got dataset with v-{dataset_json['version']}",
									    file=sys.stderr,
									)
						a_            =   dataset_json['data']

			with open(args.pred_file) as pred_file:
						a_            =   json.load(pred_file)

			a_       ,	a_            =   evaluate(dataset, predictions)

			if args.output_correct_ids:
						print(F"Output {len(correct_ids)} correctly answered question IDs.")
						with open('correct_ids.json', 'w') as f:
									json.dump(correct_ids, f)









"""simple docstring"""




# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.
from queue import Queue







def       __UpperCAmelCase      (				__UpperCamelCase					):
			__lowercase	:       int				=   Queue()
			__lowercase	:       str				=   [False] * len(__UpperCamelCase					)
			__lowercase	:       str				=   [-1] * len(__UpperCamelCase					)

			def bfs():
						while not queue.empty():
									__lowercase	:       int				=   queue.get()
									__lowercase	:       List[str]				=   True

									for neighbour in graph[u]:
												if neighbour == u:
															return False

												if color[neighbour] == -1:
															__lowercase	:       str				=   1 - color[u]
															queue.put(__UpperCamelCase					)

												elif color[neighbour] == color[u]:
															return False

						return True

			for i in range(len(__UpperCamelCase					)					):
						if not visited[i]:
									queue.put(__UpperCamelCase					)
									__lowercase	:       int				=   0
									if bfs() is False:
												return False

			return True


if __name__ == "__main__":
			# Adjacency List of graph
			print(check_bipartite({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))



