


'''simple docstring'''


from typing import Dict, List

from nltk.translate import gleu_score

import datasets
from datasets import MetricInfo


lowerCamelCase__					=   '\\n@misc{wu2016googles,\n      title={Google\'s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation},\n      author={Yonghui Wu and Mike Schuster and Zhifeng Chen and Quoc V. Le and Mohammad Norouzi and Wolfgang Macherey\n              and Maxim Krikun and Yuan Cao and Qin Gao and Klaus Macherey and Jeff Klingner and Apurva Shah and Melvin\n              Johnson and Xiaobing Liu and Łukasz Kaiser and Stephan Gouws and Yoshikiyo Kato and Taku Kudo and Hideto\n              Kazawa and Keith Stevens and George Kurian and Nishant Patil and Wei Wang and Cliff Young and\n              Jason Smith and Jason Riesa and Alex Rudnick and Oriol Vinyals and Greg Corrado and Macduff Hughes\n              and Jeffrey Dean},\n      year={2016},\n      eprint={1609.08144},\n      archivePrefix={arXiv},\n      primaryClass={cs.CL}\n}\n'

lowerCamelCase__					=   '\\nThe BLEU score has some undesirable properties when used for single\nsentences, as it was designed to be a corpus measure. We therefore\nuse a slightly different score for our RL experiments which we call\nthe \'GLEU score\'. For the GLEU score, we record all sub-sequences of\n1, 2, 3 or 4 tokens in output and target sequence (n-grams). We then\ncompute a recall, which is the ratio of the number of matching n-grams\nto the number of total n-grams in the target (ground truth) sequence,\nand a precision, which is the ratio of the number of matching n-grams\nto the number of total n-grams in the generated output sequence. Then\nGLEU score is simply the minimum of recall and precision. This GLEU\nscore\'s range is always between 0 (no matches) and 1 (all match) and\nit is symmetrical when switching output and target. According to\nour experiments, GLEU score correlates quite well with the BLEU\nmetric on a corpus level but does not have its drawbacks for our per\nsentence reward objective.\n'

lowerCamelCase__					=   '\\nComputes corpus-level Google BLEU (GLEU) score of translated segments against one or more references.\nInstead of averaging the sentence level GLEU scores (i.e. macro-average precision), Wu et al. (2016) sum up the matching\ntokens and the max of hypothesis and reference tokens for each sentence, then compute using the aggregate values.\n\nArgs:\n    predictions (list of str): list of translations to score.\n        Each translation should be tokenized into a list of tokens.\n    references (list of list of str): list of lists of references for each translation.\n        Each reference should be tokenized into a list of tokens.\n    min_len (int): The minimum order of n-gram this function should extract. Defaults to 1.\n    max_len (int): The maximum order of n-gram this function should extract. Defaults to 4.\n\nReturns:\n    \'google_bleu\': google_bleu score\n\nExamples:\n    Example 1:\n        >>> hyp1 = [\'It\', \'is\', \'a\', \'guide\', \'to\', \'action\', \'which\',\n        ...         \'ensures\', \'that\', \'the\', \'rubber\', \'duck\', \'always\',\n        ...         \'disobeys\', \'the\', \'commands\', \'of\', \'the\', \'cat\']\n        >>> ref1a = [\'It\', \'is\', \'the\', \'guiding\', \'principle\', \'which\',\n        ...          \'guarantees\', \'the\', \'rubber\', \'duck\', \'forces\', \'never\',\n        ...          \'being\', \'under\', \'the\', \'command\', \'of\', \'the\', \'cat\']\n\n        >>> hyp2 = [\'he\', \'read\', \'the\', \'book\', \'because\', \'he\', \'was\',\n        ...         \'interested\', \'in\', \'world\', \'history\']\n        >>> ref2a = [\'he\', \'was\', \'interested\', \'in\', \'world\', \'history\',\n        ...          \'because\', \'he\', \'read\', \'the\', \'book\']\n\n        >>> list_of_references = [[ref1a], [ref2a]]\n        >>> hypotheses = [hyp1, hyp2]\n        >>> google_bleu = datasets.load_metric("google_bleu")\n        >>> results = google_bleu.compute(predictions=hypotheses, references=list_of_references)\n        >>> print(round(results["google_bleu"], 2))\n        0.44\n\n    Example 2:\n        >>> hyp1 = [\'It\', \'is\', \'a\', \'guide\', \'to\', \'action\', \'which\',\n        ...         \'ensures\', \'that\', \'the\', \'rubber\', \'duck\', \'always\',\n        ...         \'disobeys\', \'the\', \'commands\', \'of\', \'the\', \'cat\']\n        >>> ref1a = [\'It\', \'is\', \'the\', \'guiding\', \'principle\', \'which\',\n        ...          \'guarantees\', \'the\', \'rubber\', \'duck\', \'forces\', \'never\',\n        ...          \'being\', \'under\', \'the\', \'command\', \'of\', \'the\', \'cat\']\n        >>> ref1b = [\'It\', \'is\', \'a\', \'guide\', \'to\', \'action\', \'that\',\n        ...          \'ensures\', \'that\', \'the\', \'rubber\', \'duck\', \'will\', \'never\',\n        ...          \'heed\', \'the\', \'cat\', \'commands\']\n        >>> ref1c = [\'It\', \'is\', \'the\', \'practical\', \'guide\', \'for\', \'the\',\n        ...          \'rubber\', \'duck\', \'army\', \'never\', \'to\', \'heed\', \'the\', \'directions\',\n        ...          \'of\', \'the\', \'cat\']\n\n        >>> hyp2 = [\'he\', \'read\', \'the\', \'book\', \'because\', \'he\', \'was\',\n        ...         \'interested\', \'in\', \'world\', \'history\']\n        >>> ref2a = [\'he\', \'was\', \'interested\', \'in\', \'world\', \'history\',\n        ...          \'because\', \'he\', \'read\', \'the\', \'book\']\n\n        >>> list_of_references = [[ref1a, ref1b, ref1c], [ref2a]]\n        >>> hypotheses = [hyp1, hyp2]\n        >>> google_bleu = datasets.load_metric("google_bleu")\n        >>> results = google_bleu.compute(predictions=hypotheses, references=list_of_references)\n        >>> print(round(results["google_bleu"], 2))\n        0.61\n\n    Example 3:\n        >>> hyp1 = [\'It\', \'is\', \'a\', \'guide\', \'to\', \'action\', \'which\',\n        ...         \'ensures\', \'that\', \'the\', \'rubber\', \'duck\', \'always\',\n        ...         \'disobeys\', \'the\', \'commands\', \'of\', \'the\', \'cat\']\n        >>> ref1a = [\'It\', \'is\', \'the\', \'guiding\', \'principle\', \'which\',\n        ...          \'guarantees\', \'the\', \'rubber\', \'duck\', \'forces\', \'never\',\n        ...          \'being\', \'under\', \'the\', \'command\', \'of\', \'the\', \'cat\']\n        >>> ref1b = [\'It\', \'is\', \'a\', \'guide\', \'to\', \'action\', \'that\',\n        ...          \'ensures\', \'that\', \'the\', \'rubber\', \'duck\', \'will\', \'never\',\n        ...          \'heed\', \'the\', \'cat\', \'commands\']\n        >>> ref1c = [\'It\', \'is\', \'the\', \'practical\', \'guide\', \'for\', \'the\',\n        ...          \'rubber\', \'duck\', \'army\', \'never\', \'to\', \'heed\', \'the\', \'directions\',\n        ...          \'of\', \'the\', \'cat\']\n\n        >>> hyp2 = [\'he\', \'read\', \'the\', \'book\', \'because\', \'he\', \'was\',\n        ...         \'interested\', \'in\', \'world\', \'history\']\n        >>> ref2a = [\'he\', \'was\', \'interested\', \'in\', \'world\', \'history\',\n        ...          \'because\', \'he\', \'read\', \'the\', \'book\']\n\n        >>> list_of_references = [[ref1a, ref1b, ref1c], [ref2a]]\n        >>> hypotheses = [hyp1, hyp2]\n        >>> google_bleu = datasets.load_metric("google_bleu")\n        >>> results = google_bleu.compute(predictions=hypotheses, references=list_of_references, min_len=2)\n        >>> print(round(results["google_bleu"], 2))\n        0.53\n\n    Example 4:\n        >>> hyp1 = [\'It\', \'is\', \'a\', \'guide\', \'to\', \'action\', \'which\',\n        ...         \'ensures\', \'that\', \'the\', \'rubber\', \'duck\', \'always\',\n        ...         \'disobeys\', \'the\', \'commands\', \'of\', \'the\', \'cat\']\n        >>> ref1a = [\'It\', \'is\', \'the\', \'guiding\', \'principle\', \'which\',\n        ...          \'guarantees\', \'the\', \'rubber\', \'duck\', \'forces\', \'never\',\n        ...          \'being\', \'under\', \'the\', \'command\', \'of\', \'the\', \'cat\']\n        >>> ref1b = [\'It\', \'is\', \'a\', \'guide\', \'to\', \'action\', \'that\',\n        ...          \'ensures\', \'that\', \'the\', \'rubber\', \'duck\', \'will\', \'never\',\n        ...          \'heed\', \'the\', \'cat\', \'commands\']\n        >>> ref1c = [\'It\', \'is\', \'the\', \'practical\', \'guide\', \'for\', \'the\',\n        ...          \'rubber\', \'duck\', \'army\', \'never\', \'to\', \'heed\', \'the\', \'directions\',\n        ...          \'of\', \'the\', \'cat\']\n\n        >>> hyp2 = [\'he\', \'read\', \'the\', \'book\', \'because\', \'he\', \'was\',\n        ...         \'interested\', \'in\', \'world\', \'history\']\n        >>> ref2a = [\'he\', \'was\', \'interested\', \'in\', \'world\', \'history\',\n        ...          \'because\', \'he\', \'read\', \'the\', \'book\']\n\n        >>> list_of_references = [[ref1a, ref1b, ref1c], [ref2a]]\n        >>> hypotheses = [hyp1, hyp2]\n        >>> google_bleu = datasets.load_metric("google_bleu")\n        >>> results = google_bleu.compute(predictions=hypotheses,references=list_of_references, min_len=2, max_len=6)\n        >>> print(round(results["google_bleu"], 2))\n        0.4\n'






@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION			,				_KWARGS_DESCRIPTION		)
class 		lowerCAmelCase__	(	datasets.Metric		):




			def 							lowerCAmelCase__			(						self     :   int       )      ->MetricInfo:



					'''simple docstring'''







					return datasets.MetricInfo(
					    description=_DESCRIPTION		,     citation=_CITATION		,     inputs_description=_KWARGS_DESCRIPTION		,     features=datasets.Features(
					        {
					            "predictions": datasets.Sequence(datasets.Value("string"		,     id="token"       )		,     id="sequence"       ),
					            "references": datasets.Sequence(
					                datasets.Sequence(datasets.Value("string"		,     id="token"       )		,     id="sequence"       )		,     id="references"       ),
					        }       )		,     )






			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   List[List[List[str]]]		,     lowerCamelCase__     :   List[List[str]]		,     lowerCamelCase__     :   int = 1		,     lowerCamelCase__     :   int = 4		,     )      ->Dict[str, float]:



					'''simple docstring'''







					return {
					    "google_bleu": gleu_score.corpus_gleu(
					        list_of_references=lowerCamelCase__		,     hypotheses=lowerCamelCase__		,     min_len=lowerCamelCase__		,     max_len=lowerCamelCase__       )
					}







'''simple docstring'''


from collections import deque
from math import floor
from random import random
from time import time






class 		lowerCAmelCase__	:




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



					'''simple docstring'''







					_UpperCAmelCase						:				List[Any]	    =					{}




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   Tuple		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   int=1       )      ->Optional[Any]:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							if self.graph[u].count([w, v]       ) == 0:
									self.graph[u].append([w, v]       )
					else:
							_UpperCAmelCase						:				Dict	    =					[[w, v]]
					if not self.graph.get(lowerCamelCase__       ):
							_UpperCAmelCase						:				str	    =					[]




			def 							lowerCAmelCase__			(						self     :   Any       )      ->Tuple:



					'''simple docstring'''







					return list(self.graph       )




			def 							lowerCAmelCase__			(						self     :   Tuple		,     lowerCamelCase__     :   Union[str, Any]		,     lowerCamelCase__     :   str       )      ->Any:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							for _ in self.graph[u]:
									if _[1] == v:
											self.graph[u].remove(lowerCamelCase__       )




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Optional[Any]=-2		,     lowerCamelCase__     :   Optional[int]=-1       )      ->int:



					'''simple docstring'''







					if s == d:
							return []
					_UpperCAmelCase						:				Tuple	    =					[]
					_UpperCAmelCase						:				Optional[int]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				Union[str, Any]	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				Optional[Any]	    =					s

					while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]       ) != 0:
									_UpperCAmelCase						:				str	    =					s
									for node in self.graph[s]:
											if visited.count(node[1]       ) < 1:
													if node[1] == d:
															visited.append(lowerCamelCase__       )
															return visited
													else:
															stack.append(node[1]       )
															visited.append(node[1]       )
															_UpperCAmelCase						:				Union[str, Any]	    =					node[1]
															break

            # check if all the children are visited
							if s == ss:
									stack.pop()
									if len(lowerCamelCase__       ) != 0:
											_UpperCAmelCase						:				Tuple	    =					stack[len(lowerCamelCase__       ) - 1]
							else:
									_UpperCAmelCase						:				Optional[int]	    =					ss

							# check if se have reached the starting point
							if len(lowerCamelCase__       ) == 0:
									return visited




			def 							lowerCAmelCase__			(						self     :   List[Any]		,     lowerCamelCase__     :   Any=-1       )      ->str:



					'''simple docstring'''







					if c == -1:
							_UpperCAmelCase						:				str	    =					floor(random() * 1_00_00       ) + 10
					for i in range(lowerCamelCase__       ):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 1_02       ) + 1       ):
									_UpperCAmelCase						:				Tuple	    =					floor(random() * c       ) + 1
									if n != i:
											self.add_pair(lowerCamelCase__		,     lowerCamelCase__		,     1       )




			def 							lowerCAmelCase__			(						self     :   Any		,     lowerCamelCase__     :   Union[str, Any]=-2       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				List[str]	    =					deque()
					_UpperCAmelCase						:				int	    =					[]
					if s == -2:
							_UpperCAmelCase						:				str	    =					list(self.graph       )[0]
					d.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					while d:
							_UpperCAmelCase						:				int	    =					d.popleft()
							if len(self.graph[s]       ) != 0:
									for node in self.graph[s]:
											if visited.count(node[1]       ) < 1:
													d.append(node[1]       )
													visited.append(node[1]       )
					return visited




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   Union[str, Any]       )      ->Dict:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					0
					for x in self.graph:
							for y in self.graph[x]:
									if y[1] == u:
											count += 1
					return count




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Union[str, Any]       )      ->int:



					'''simple docstring'''







					return len(self.graph[u]       )




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Any=-2       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					[]
					_UpperCAmelCase						:				List[str]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				str	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				List[Any]	    =					s
					_UpperCAmelCase						:				Tuple	    =					[]

					while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]       ) != 0:
									_UpperCAmelCase						:				str	    =					s
									for node in self.graph[s]:
											if visited.count(node[1]       ) < 1:
													stack.append(node[1]       )
													visited.append(node[1]       )
													_UpperCAmelCase						:				List[Any]	    =					node[1]
													break

            # check if all the children are visited
							if s == ss:
									sorted_nodes.append(stack.pop()       )
									if len(lowerCamelCase__       ) != 0:
											_UpperCAmelCase						:				Dict	    =					stack[len(lowerCamelCase__       ) - 1]
							else:
									_UpperCAmelCase						:				List[str]	    =					ss

							# check if se have reached the starting point
							if len(lowerCamelCase__       ) == 0:
									return sorted_nodes




			def 							lowerCAmelCase__			(						self     :   Union[str, Any]       )      ->Optional[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Tuple	    =					[]
					_UpperCAmelCase						:				str	    =					[]
					_UpperCAmelCase						:				int	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				str	    =					-2
					_UpperCAmelCase						:				Optional[int]	    =					[]
					_UpperCAmelCase						:				Union[str, Any]	    =					s
					_UpperCAmelCase						:				Tuple	    =					False
					_UpperCAmelCase						:				List[str]	    =					set()

					while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]       ) != 0:
									_UpperCAmelCase						:				Optional[Any]	    =					s
									for node in self.graph[s]:
											if (
											    visited.count(node[1]       ) > 0
											    and node[1] != parent
											    and indirect_parents.count(node[1]       ) > 0
											    and not on_the_way_back
											):
													_UpperCAmelCase						:				Optional[int]	    =					len(lowerCamelCase__       ) - 1
													while len_stack >= 0:
															if stack[len_stack] == node[1]:
																	anticipating_nodes.add(node[1]       )
																	break
															else:
																	anticipating_nodes.add(stack[len_stack]       )
																	len_stack -= 1
											if visited.count(node[1]       ) < 1:
													stack.append(node[1]       )
													visited.append(node[1]       )
													_UpperCAmelCase						:				Dict	    =					node[1]
													break

            # check if all the children are visited
							if s == ss:
									stack.pop()
									_UpperCAmelCase						:				List[str]	    =					True
									if len(lowerCamelCase__       ) != 0:
											_UpperCAmelCase						:				Tuple	    =					stack[len(lowerCamelCase__       ) - 1]
							else:
									_UpperCAmelCase						:				Optional[Any]	    =					False
									indirect_parents.append(lowerCamelCase__       )
									_UpperCAmelCase						:				Any	    =					s
									_UpperCAmelCase						:				Dict	    =					ss

							# check if se have reached the starting point
							if len(lowerCamelCase__       ) == 0:
									return list(lowerCamelCase__       )




			def 							lowerCAmelCase__			(						self     :   int       )      ->Optional[int]:



					'''simple docstring'''







					_UpperCAmelCase						:				Union[str, Any]	    =					[]
					_UpperCAmelCase						:				Optional[Any]	    =					[]
					_UpperCAmelCase						:				str	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				Any	    =					-2
					_UpperCAmelCase						:				Optional[Any]	    =					[]
					_UpperCAmelCase						:				Tuple	    =					s
					_UpperCAmelCase						:				List[str]	    =					False
					_UpperCAmelCase						:				Optional[Any]	    =					set()

					while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]       ) != 0:
									_UpperCAmelCase						:				Optional[int]	    =					s
									for node in self.graph[s]:
											if (
											    visited.count(node[1]       ) > 0
											    and node[1] != parent
											    and indirect_parents.count(node[1]       ) > 0
											    and not on_the_way_back
											):
													_UpperCAmelCase						:				Optional[int]	    =					len(lowerCamelCase__       ) - 1
													while len_stack_minus_one >= 0:
															if stack[len_stack_minus_one] == node[1]:
																	anticipating_nodes.add(node[1]       )
																	break
															else:
																	return True
											if visited.count(node[1]       ) < 1:
													stack.append(node[1]       )
													visited.append(node[1]       )
													_UpperCAmelCase						:				Tuple	    =					node[1]
													break

            # check if all the children are visited
							if s == ss:
									stack.pop()
									_UpperCAmelCase						:				Dict	    =					True
									if len(lowerCamelCase__       ) != 0:
											_UpperCAmelCase						:				List[str]	    =					stack[len(lowerCamelCase__       ) - 1]
							else:
									_UpperCAmelCase						:				Union[str, Any]	    =					False
									indirect_parents.append(lowerCamelCase__       )
									_UpperCAmelCase						:				Optional[Any]	    =					s
									_UpperCAmelCase						:				Optional[Any]	    =					ss

							# check if se have reached the starting point
							if len(lowerCamelCase__       ) == 0:
									return False




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   Tuple=-2		,     lowerCamelCase__     :   Union[str, Any]=-1       )      ->Any:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					time()
					self.dfs(lowerCamelCase__		,     lowerCamelCase__       )
					_UpperCAmelCase						:				Tuple	    =					time()
					return end - begin






			def 							lowerCAmelCase__			(						self     :   List[Any]		,     lowerCamelCase__     :   Dict=-2       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.bfs(lowerCamelCase__       )
					_UpperCAmelCase						:				Tuple	    =					time()
					return end - begin






class 		lowerCAmelCase__	:




			def __init__(						self     :   Tuple       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Any	    =					{}




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   List[str]		,     lowerCamelCase__     :   str		,     lowerCamelCase__     :   Tuple=1       )      ->int:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							# if there already is a edge
							if self.graph[u].count([w, v]       ) == 0:
									self.graph[u].append([w, v]       )
					else:
							# if u does not exist
							_UpperCAmelCase						:				Dict	    =					[[w, v]]
					# add the other way
					if self.graph.get(lowerCamelCase__       ):
							# if there already is a edge
							if self.graph[v].count([w, u]       ) == 0:
									self.graph[v].append([w, u]       )
					else:
							# if u does not exist
							_UpperCAmelCase						:				Tuple	    =					[[w, u]]




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   Any		,     lowerCamelCase__     :   Optional[Any]       )      ->Dict:



					'''simple docstring'''







					if self.graph.get(lowerCamelCase__       ):
							for _ in self.graph[u]:
									if _[1] == v:
											self.graph[u].remove(lowerCamelCase__       )
        # the other way round
					if self.graph.get(lowerCamelCase__       ):
							for _ in self.graph[v]:
									if _[1] == u:
											self.graph[v].remove(lowerCamelCase__       )




			def 							lowerCAmelCase__			(						self     :   List[str]		,     lowerCamelCase__     :   List[str]=-2		,     lowerCamelCase__     :   List[str]=-1       )      ->List[Any]:



					'''simple docstring'''







					if s == d:
							return []
					_UpperCAmelCase						:				List[Any]	    =					[]
					_UpperCAmelCase						:				List[Any]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				List[Any]	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				List[Any]	    =					s

					while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]       ) != 0:
									_UpperCAmelCase						:				Optional[Any]	    =					s
									for node in self.graph[s]:
											if visited.count(node[1]       ) < 1:
													if node[1] == d:
															visited.append(lowerCamelCase__       )
															return visited
													else:
															stack.append(node[1]       )
															visited.append(node[1]       )
															_UpperCAmelCase						:				Optional[int]	    =					node[1]
															break

            # check if all the children are visited
							if s == ss:
									stack.pop()
									if len(lowerCamelCase__       ) != 0:
											_UpperCAmelCase						:				Optional[int]	    =					stack[len(lowerCamelCase__       ) - 1]
							else:
									_UpperCAmelCase						:				Union[str, Any]	    =					ss

							# check if se have reached the starting point
							if len(lowerCamelCase__       ) == 0:
									return visited




			def 							lowerCAmelCase__			(						self     :   Any		,     lowerCamelCase__     :   Dict=-1       )      ->str:



					'''simple docstring'''







					if c == -1:
							_UpperCAmelCase						:				str	    =					floor(random() * 1_00_00       ) + 10
					for i in range(lowerCamelCase__       ):
							# every vertex has max 100 edges
							for _ in range(floor(random() * 1_02       ) + 1       ):
									_UpperCAmelCase						:				str	    =					floor(random() * c       ) + 1
									if n != i:
											self.add_pair(lowerCamelCase__		,     lowerCamelCase__		,     1       )




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   Union[str, Any]=-2       )      ->Any:



					'''simple docstring'''







					_UpperCAmelCase						:				str	    =					deque()
					_UpperCAmelCase						:				Optional[int]	    =					[]
					if s == -2:
							_UpperCAmelCase						:				Union[str, Any]	    =					list(self.graph       )[0]
					d.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					while d:
							_UpperCAmelCase						:				Any	    =					d.popleft()
							if len(self.graph[s]       ) != 0:
									for node in self.graph[s]:
											if visited.count(node[1]       ) < 1:
													d.append(node[1]       )
													visited.append(node[1]       )
					return visited




			def 							lowerCAmelCase__			(						self     :   Union[str, Any]		,     lowerCamelCase__     :   Dict       )      ->Optional[Any]:



					'''simple docstring'''







					return len(self.graph[u]       )




			def 							lowerCAmelCase__			(						self     :   str       )      ->Any:



					'''simple docstring'''







					_UpperCAmelCase						:				int	    =					[]
					_UpperCAmelCase						:				str	    =					[]
					_UpperCAmelCase						:				Optional[int]	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				Any	    =					-2
					_UpperCAmelCase						:				Union[str, Any]	    =					[]
					_UpperCAmelCase						:				str	    =					s
					_UpperCAmelCase						:				int	    =					False
					_UpperCAmelCase						:				List[Any]	    =					set()

					while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]       ) != 0:
									_UpperCAmelCase						:				int	    =					s
									for node in self.graph[s]:
											if (
											    visited.count(node[1]       ) > 0
											    and node[1] != parent
											    and indirect_parents.count(node[1]       ) > 0
											    and not on_the_way_back
											):
													_UpperCAmelCase						:				Union[str, Any]	    =					len(lowerCamelCase__       ) - 1
													while len_stack >= 0:
															if stack[len_stack] == node[1]:
																	anticipating_nodes.add(node[1]       )
																	break
															else:
																	anticipating_nodes.add(stack[len_stack]       )
																	len_stack -= 1
											if visited.count(node[1]       ) < 1:
													stack.append(node[1]       )
													visited.append(node[1]       )
													_UpperCAmelCase						:				Union[str, Any]	    =					node[1]
													break

            # check if all the children are visited
							if s == ss:
									stack.pop()
									_UpperCAmelCase						:				List[Any]	    =					True
									if len(lowerCamelCase__       ) != 0:
											_UpperCAmelCase						:				List[str]	    =					stack[len(lowerCamelCase__       ) - 1]
							else:
									_UpperCAmelCase						:				Dict	    =					False
									indirect_parents.append(lowerCamelCase__       )
									_UpperCAmelCase						:				Dict	    =					s
									_UpperCAmelCase						:				Dict	    =					ss

							# check if se have reached the starting point
							if len(lowerCamelCase__       ) == 0:
									return list(lowerCamelCase__       )




			def 							lowerCAmelCase__			(						self     :   Optional[Any]       )      ->Dict:



					'''simple docstring'''







					_UpperCAmelCase						:				List[Any]	    =					[]
					_UpperCAmelCase						:				List[str]	    =					[]
					_UpperCAmelCase						:				Tuple	    =					list(self.graph       )[0]
					stack.append(lowerCamelCase__       )
					visited.append(lowerCamelCase__       )
					_UpperCAmelCase						:				Dict	    =					-2
					_UpperCAmelCase						:				Union[str, Any]	    =					[]
					_UpperCAmelCase						:				Dict	    =					s
					_UpperCAmelCase						:				Dict	    =					False
					_UpperCAmelCase						:				str	    =					set()

					while True:
							# check if there is any non isolated nodes
							if len(self.graph[s]       ) != 0:
									_UpperCAmelCase						:				Union[str, Any]	    =					s
									for node in self.graph[s]:
											if (
											    visited.count(node[1]       ) > 0
											    and node[1] != parent
											    and indirect_parents.count(node[1]       ) > 0
											    and not on_the_way_back
											):
													_UpperCAmelCase						:				int	    =					len(lowerCamelCase__       ) - 1
													while len_stack_minus_one >= 0:
															if stack[len_stack_minus_one] == node[1]:
																	anticipating_nodes.add(node[1]       )
																	break
															else:
																	return True
											if visited.count(node[1]       ) < 1:
													stack.append(node[1]       )
													visited.append(node[1]       )
													_UpperCAmelCase						:				Union[str, Any]	    =					node[1]
													break

            # check if all the children are visited
							if s == ss:
									stack.pop()
									_UpperCAmelCase						:				List[Any]	    =					True
									if len(lowerCamelCase__       ) != 0:
											_UpperCAmelCase						:				List[Any]	    =					stack[len(lowerCamelCase__       ) - 1]
							else:
									_UpperCAmelCase						:				Optional[Any]	    =					False
									indirect_parents.append(lowerCamelCase__       )
									_UpperCAmelCase						:				List[str]	    =					s
									_UpperCAmelCase						:				List[Any]	    =					ss

							# check if se have reached the starting point
							if len(lowerCamelCase__       ) == 0:
									return False




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



					'''simple docstring'''







					return list(self.graph       )




			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Dict=-2		,     lowerCamelCase__     :   Dict=-1       )      ->List[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.dfs(lowerCamelCase__		,     lowerCamelCase__       )
					_UpperCAmelCase						:				int	    =					time()
					return end - begin






			def 							lowerCAmelCase__			(						self     :   int		,     lowerCamelCase__     :   Any=-2       )      ->int:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					time()
					self.bfs(lowerCamelCase__       )
					_UpperCAmelCase						:				Any	    =					time()
					return end - begin



