


'''simple docstring'''







import argparse
import collections
import json
import os
import re
import string
import sys

import numpy as np


a__  :					Optional[int]        =       re.compile(R'\b(a|an|the)\b', re.UNICODE)

a__  :					int        =       None







def _UpperCamelCase       (     )							->		Dict:


      '''simple docstring'''



      UpperCamelCase__										=				argparse.ArgumentParser("Official evaluation script for SQuAD version 2.0."    )
      parser.add_argument("data_file"      ,			metavar="data.json"      ,			help="Input data JSON file."    )
      parser.add_argument("pred_file"      ,			metavar="pred.json"      ,			help="Model predictions."    )
      parser.add_argument(
          "--out-file"      ,			"-o"      ,			metavar="eval.json"      ,			help="Write accuracy metrics to file (default is stdout)."    )
      parser.add_argument(
          "--na-prob-file"      ,			"-n"      ,			metavar="na_prob.json"      ,			help="Model estimates of probability of no answer."    )
      parser.add_argument(
          "--na-prob-thresh"      ,			"-t"      ,			type=__A      ,			default=1.0      ,			help="Predict \"\" if no-answer probability exceeds this (default = 1.0)."      ,			)
      parser.add_argument(
          "--out-image-dir"      ,			"-p"      ,			metavar="out_images"      ,			default=__A      ,			help="Save precision-recall curves to directory."    )
      parser.add_argument("--verbose"      ,			"-v"      ,			action="store_true"    )
      if len(sys.argv    ) == 1:
            parser.print_help()
            sys.exit(1    )
      return parser.parse_args()







def _UpperCamelCase       (     __A    )							->		Dict:


      '''simple docstring'''



      UpperCamelCase__										=				{}
      for article in dataset:
            for p in article["paragraphs"]:
                  for qa in p["qas"]:
                        UpperCamelCase__										=				bool(qa["answers"]["text"]    )
      return qid_to_has_ans







def _UpperCamelCase       (     __A    )							->		Optional[Any]:


      '''simple docstring'''



      def remove_articles(__A    ):
            return ARTICLES_REGEX.sub(" "      ,			__A    )

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

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

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

      return white_space_fix(remove_articles(remove_punc(lower(__A    )    )    )    )







def _UpperCamelCase       (     __A    )							->		int:


      '''simple docstring'''



      if not s:
            return []
      return normalize_answer(__A    ).split()







def _UpperCamelCase       (     __A      ,			__A    )							->		List[Any]:


      '''simple docstring'''



      return int(normalize_answer(__A    ) == normalize_answer(__A    )    )







def _UpperCamelCase       (     __A      ,			__A    )							->		Optional[int]:


      '''simple docstring'''



      UpperCamelCase__										=				get_tokens(__A    )
      UpperCamelCase__										=				get_tokens(__A    )
      UpperCamelCase__										=				collections.Counter(__A    ) & collections.Counter(__A    )
      UpperCamelCase__										=				sum(common.values()    )
      if len(__A    ) == 0 or len(__A    ) == 0:
            # If either is no-answer, then F1 is 1 if they agree, 0 otherwise
            return int(gold_toks == pred_toks    )
      if num_same == 0:
            return 0
      UpperCamelCase__										=				1.0 * num_same / len(__A    )
      UpperCamelCase__										=				1.0 * num_same / len(__A    )
      UpperCamelCase__										=				(2 * precision * recall) / (precision + recall)
      return fa







def _UpperCamelCase       (     __A      ,			__A    )							->		Union[str, Any]:


      '''simple docstring'''



      UpperCamelCase__										=				{}
      UpperCamelCase__										=				{}
      for article in dataset:
            for p in article["paragraphs"]:
                  for qa in p["qas"]:
                        UpperCamelCase__										=				qa["id"]
                        UpperCamelCase__										=				[t for t in qa["answers"]["text"] if normalize_answer(__A    )]
                        if not gold_answers:
                              # For unanswerable questions, only correct answer is empty string
                              UpperCamelCase__										=				[""]
                        if qid not in preds:
                              print(F'''Missing prediction for {qid}'''    )
                              continue
                        UpperCamelCase__										=				preds[qid]
                        # Take max over all gold answers
                        UpperCamelCase__										=				max(compute_exact(__A      ,			__A    ) for a in gold_answers    )
                        UpperCamelCase__										=				max(compute_fa(__A      ,			__A    ) for a in gold_answers    )
      return exact_scores, fa_scores







def _UpperCamelCase       (     __A      ,			__A      ,			__A      ,			__A    )							->		Union[str, Any]:


      '''simple docstring'''



      UpperCamelCase__										=				{}
      for qid, s in scores.items():
            UpperCamelCase__										=				na_probs[qid] > na_prob_thresh
            if pred_na:
                  UpperCamelCase__										=				float(not qid_to_has_ans[qid]    )
            else:
                  UpperCamelCase__										=				s
      return new_scores







def _UpperCamelCase       (     __A      ,			__A      ,			__A=None    )							->		List[Any]:


      '''simple docstring'''



      if not qid_list:
            UpperCamelCase__										=				len(__A    )
            return collections.OrderedDict(
                [
                    ("exact", 100.0 * sum(exact_scores.values()    ) / total),
                    ("f1", 100.0 * sum(fa_scores.values()    ) / total),
                    ("total", total),
                ]    )
      else:
            UpperCamelCase__										=				len(__A    )
            return collections.OrderedDict(
                [
                    ("exact", 100.0 * sum(exact_scores[k] for k in qid_list    ) / total),
                    ("f1", 100.0 * sum(fa_scores[k] for k in qid_list    ) / total),
                    ("total", total),
                ]    )







def _UpperCamelCase       (     __A      ,			__A      ,			__A    )							->		Optional[int]:


      '''simple docstring'''



      for k in new_eval:
            UpperCamelCase__										=				new_eval[k]







def _UpperCamelCase       (     __A      ,			__A      ,			__A      ,			__A    )							->		Optional[int]:


      '''simple docstring'''



      plt.step(__A      ,			__A      ,			color="b"      ,			alpha=0.2      ,			where="post"    )
      plt.fill_between(__A      ,			__A      ,			step="post"      ,			alpha=0.2      ,			color="b"    )
      plt.xlabel("Recall"    )
      plt.ylabel("Precision"    )
      plt.xlim([0.0, 1.05]    )
      plt.ylim([0.0, 1.05]    )
      plt.title(__A    )
      plt.savefig(__A    )
      plt.clf()







def _UpperCamelCase       (     __A      ,			__A      ,			__A      ,			__A      ,			__A=None      ,			__A=None    )							->		Any:


      '''simple docstring'''



      UpperCamelCase__										=				sorted(__A      ,			key=lambda __A    : na_probs[k]    )
      UpperCamelCase__										=				0.0
      UpperCamelCase__										=				1.0
      UpperCamelCase__										=				0.0
      UpperCamelCase__										=				[1.0]
      UpperCamelCase__										=				[0.0]
      UpperCamelCase__										=				0.0
      for i, qid in enumerate(__A    ):
            if qid_to_has_ans[qid]:
                  true_pos += scores[qid]
            UpperCamelCase__										=				true_pos / float(i + 1    )
            UpperCamelCase__										=				true_pos / float(__A    )
            if i == len(__A    ) - 1 or na_probs[qid] != na_probs[qid_list[i + 1]]:
                  # i.e., if we can put a threshold after this point
                  avg_prec += cur_p * (cur_r - recalls[-1])
                  precisions.append(__A    )
                  recalls.append(__A    )
      if out_image:
            plot_pr_curve(__A      ,			__A      ,			__A      ,			__A    )
      return {"ap": 100.0 * avg_prec}







def _UpperCamelCase       (     __A      ,			__A      ,			__A      ,			__A      ,			__A      ,			__A    )							->		List[str]:


      '''simple docstring'''



      if out_image_dir and not os.path.exists(__A    ):
            os.makedirs(__A    )
      UpperCamelCase__										=				sum(1 for v in qid_to_has_ans.values() if v    )
      if num_true_pos == 0:
            return
      UpperCamelCase__										=				make_precision_recall_eval(
          __A      ,			__A      ,			__A      ,			__A      ,			out_image=os.path.join(__A      ,			"pr_exact.png"    )      ,			title="Precision-Recall curve for Exact Match score"      ,			)
      UpperCamelCase__										=				make_precision_recall_eval(
          __A      ,			__A      ,			__A      ,			__A      ,			out_image=os.path.join(__A      ,			"pr_f1.png"    )      ,			title="Precision-Recall curve for F1 score"      ,			)
      UpperCamelCase__										=				{k: float(__A    ) for k, v in qid_to_has_ans.items()}
      UpperCamelCase__										=				make_precision_recall_eval(
          __A      ,			__A      ,			__A      ,			__A      ,			out_image=os.path.join(__A      ,			"pr_oracle.png"    )      ,			title="Oracle Precision-Recall curve (binary task of HasAns vs. NoAns)"      ,			)
      merge_eval(__A      ,			__A      ,			"pr_exact"    )
      merge_eval(__A      ,			__A      ,			"pr_f1"    )
      merge_eval(__A      ,			__A      ,			"pr_oracle"    )







def _UpperCamelCase       (     __A      ,			__A      ,			__A      ,			__A    )							->		List[str]:


      '''simple docstring'''



      if not qid_list:
            return
      UpperCamelCase__										=				[na_probs[k] for k in qid_list]
      UpperCamelCase__										=				np.ones_like(__A    ) / float(len(__A    )    )
      plt.hist(__A      ,			weights=__A      ,			bins=20      ,			range=(0.0, 1.0)    )
      plt.xlabel("Model probability of no-answer"    )
      plt.ylabel("Proportion of dataset"    )
      plt.title(F'''Histogram of no-answer probability: {name}'''    )
      plt.savefig(os.path.join(__A      ,			F'''na_prob_hist_{name}.png'''    )    )
      plt.clf()







def _UpperCamelCase       (     __A      ,			__A      ,			__A      ,			__A    )							->		Tuple:


      '''simple docstring'''



      UpperCamelCase__										=				sum(1 for k in qid_to_has_ans if not qid_to_has_ans[k]    )
      UpperCamelCase__										=				num_no_ans
      UpperCamelCase__										=				cur_score
      UpperCamelCase__										=				0.0
      UpperCamelCase__										=				sorted(__A      ,			key=lambda __A    : na_probs[k]    )
      for i, qid in enumerate(__A    ):
            if qid not in scores:
                  continue
            if qid_to_has_ans[qid]:
                  UpperCamelCase__										=				scores[qid]
            else:
                  if preds[qid]:
                        UpperCamelCase__										=				-1
                  else:
                        UpperCamelCase__										=				0
            cur_score += diff
            if cur_score > best_score:
                  UpperCamelCase__										=				cur_score
                  UpperCamelCase__										=				na_probs[qid]
      return 100.0 * best_score / len(__A    ), best_thresh







def _UpperCamelCase       (     __A      ,			__A      ,			__A      ,			__A      ,			__A      ,			__A    )							->		Dict:


      '''simple docstring'''



      UpperCamelCase__					,	UpperCamelCase__										=				find_best_thresh(__A      ,			__A      ,			__A      ,			__A    )
      UpperCamelCase__					,	UpperCamelCase__										=				find_best_thresh(__A      ,			__A      ,			__A      ,			__A    )
      UpperCamelCase__										=				best_exact
      UpperCamelCase__										=				exact_thresh
      UpperCamelCase__										=				best_fa
      UpperCamelCase__										=				fa_thresh







def _UpperCamelCase       (     )							->		Any:


      '''simple docstring'''



      with open(OPTS.data_file    ) as f:
            UpperCamelCase__										=				json.load(__A    )
            UpperCamelCase__										=				dataset_json["data"]
      with open(OPTS.pred_file    ) as f:
            UpperCamelCase__										=				json.load(__A    )
      if OPTS.na_prob_file:
            with open(OPTS.na_prob_file    ) as f:
                  UpperCamelCase__										=				json.load(__A    )
      else:
            UpperCamelCase__										=				{k: 0.0 for k in preds}
      UpperCamelCase__										=				make_qid_to_has_ans(__A    )  # maps qid to True/False
      UpperCamelCase__										=				[k for k, v in qid_to_has_ans.items() if v]
      UpperCamelCase__										=				[k for k, v in qid_to_has_ans.items() if not v]
      UpperCamelCase__					,	UpperCamelCase__										=				get_raw_scores(__A      ,			__A    )
      UpperCamelCase__										=				apply_no_ans_threshold(__A      ,			__A      ,			__A      ,			OPTS.na_prob_thresh    )
      UpperCamelCase__										=				apply_no_ans_threshold(__A      ,			__A      ,			__A      ,			OPTS.na_prob_thresh    )
      UpperCamelCase__										=				make_eval_dict(__A      ,			__A    )
      if has_ans_qids:
            UpperCamelCase__										=				make_eval_dict(__A      ,			__A      ,			qid_list=__A    )
            merge_eval(__A      ,			__A      ,			"HasAns"    )
      if no_ans_qids:
            UpperCamelCase__										=				make_eval_dict(__A      ,			__A      ,			qid_list=__A    )
            merge_eval(__A      ,			__A      ,			"NoAns"    )
      if OPTS.na_prob_file:
            find_all_best_thresh(__A      ,			__A      ,			__A      ,			__A      ,			__A      ,			__A    )
      if OPTS.na_prob_file and OPTS.out_image_dir:
            run_precision_recall_analysis(__A      ,			__A      ,			__A      ,			__A      ,			__A      ,			OPTS.out_image_dir    )
            histogram_na_prob(__A      ,			__A      ,			OPTS.out_image_dir      ,			"hasAns"    )
            histogram_na_prob(__A      ,			__A      ,			OPTS.out_image_dir      ,			"noAns"    )
      if OPTS.out_file:
            with open(OPTS.out_file      ,			"w"    ) as f:
                  json.dump(__A      ,			__A    )
      else:
            print(json.dumps(__A      ,			indent=2    )    )


if __name__ == "__main__":
  a__  :					Optional[int]        =       parse_args()
  if OPTS.out_image_dir:
    import matplotlib

    matplotlib.use('Agg')
    import matplotlib.pyplot as plt
  main()












"""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.






def 					A__				(			UpperCamelCase       ):
							A		=  [False] * len(UpperCamelCase       )
							A		=  [-1] * len(UpperCamelCase       )

							def dfs(UpperCamelCase					,  UpperCamelCase       ):
														A		=  True
														A		=  c
														for u in graph[v]:
																					if not visited[u]:
																												dfs(UpperCamelCase					,  1 - c       )

							for i in range(len(UpperCamelCase       )       ):
														if not visited[i]:
																					dfs(UpperCamelCase					,  0       )

							for i in range(len(UpperCamelCase       )       ):
														for j in graph[i]:
																					if color[i] == color[j]:
																												return False

							return True


# Adjacency list of graph
_snake_case     :		str       						= {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2], 4: []}
print(check_bipartite_dfs(graph))


