


'''simple docstring'''


import json
import os
import shutil
import tempfile
from unittest import TestCase

from transformers import BartTokenizer, BartTokenizerFast, DPRQuestionEncoderTokenizer, DPRQuestionEncoderTokenizerFast
from transformers.models.bart.configuration_bart import BartConfig
from transformers.models.bert.tokenization_bert import VOCAB_FILES_NAMES as DPR_VOCAB_FILES_NAMES
from transformers.models.dpr.configuration_dpr import DPRConfig
from transformers.models.roberta.tokenization_roberta import VOCAB_FILES_NAMES as BART_VOCAB_FILES_NAMES
from transformers.testing_utils import require_faiss, require_tokenizers, require_torch, slow
from transformers.utils import is_datasets_available, is_faiss_available, is_torch_available


if is_torch_available() and is_datasets_available() and is_faiss_available():
						from transformers.models.rag.configuration_rag import RagConfig
						from transformers.models.rag.tokenization_rag import RagTokenizer






@require_faiss
@require_torch
class 		lowerCAmelCase__	(	UpperCAmelCase__		):




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



					'''simple docstring'''







					_UpperCAmelCase						:				List[str]	    =					tempfile.mkdtemp()
					_UpperCAmelCase						:				Dict	    =					8

					# DPR tok
					_UpperCAmelCase						:				List[str]	    =					[
					    "[UNK]",
					    "[CLS]",
					    "[SEP]",
					    "[PAD]",
					    "[MASK]",
					    "want",
					    "##want",
					    "##ed",
					    "wa",
					    "un",
					    "runn",
					    "##ing",
					    ",",
					    "low",
					    "lowest",
					]
					_UpperCAmelCase						:				Optional[Any]	    =					os.path.join(self.tmpdirname		,     "dpr_tokenizer"       )
					os.makedirs(lowerCamelCase__		,     exist_ok=lowerCamelCase__       )
					_UpperCAmelCase						:				Optional[int]	    =					os.path.join(lowerCamelCase__		,     DPR_VOCAB_FILES_NAMES["vocab_file"]       )
					with open(self.vocab_file		,     "w"		,     encoding="utf-8"       ) as vocab_writer:
							vocab_writer.write("".join([x + "\n" for x in vocab_tokens]       )       )

					# BART tok
					_UpperCAmelCase						:				List[str]	    =					[
					    "l",
					    "o",
					    "w",
					    "e",
					    "r",
					    "s",
					    "t",
					    "i",
					    "d",
					    "n",
					    "\u0120",
					    "\u0120l",
					    "\u0120n",
					    "\u0120lo",
					    "\u0120low",
					    "er",
					    "\u0120lowest",
					    "\u0120newer",
					    "\u0120wider",
					    "<unk>",
					]
					_UpperCAmelCase						:				Tuple	    =					dict(zip(lowerCamelCase__		,     range(len(lowerCamelCase__       )       )       )       )
					_UpperCAmelCase						:				str	    =					["#version: 0.2", "\u0120 l", "\u0120l o", "\u0120lo w", "e r", ""]
					_UpperCAmelCase						:				Any	    =					{"unk_token": "<unk>"}

					_UpperCAmelCase						:				Optional[Any]	    =					os.path.join(self.tmpdirname		,     "bart_tokenizer"       )
					os.makedirs(lowerCamelCase__		,     exist_ok=lowerCamelCase__       )
					_UpperCAmelCase						:				Any	    =					os.path.join(lowerCamelCase__		,     BART_VOCAB_FILES_NAMES["vocab_file"]       )
					_UpperCAmelCase						:				List[Any]	    =					os.path.join(lowerCamelCase__		,     BART_VOCAB_FILES_NAMES["merges_file"]       )
					with open(self.vocab_file		,     "w"		,     encoding="utf-8"       ) as fp:
							fp.write(json.dumps(lowerCamelCase__       ) + "\n"       )
					with open(self.merges_file		,     "w"		,     encoding="utf-8"       ) as fp:
							fp.write("\n".join(lowerCamelCase__       )       )




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



					'''simple docstring'''







					return DPRQuestionEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname		,     "dpr_tokenizer"       )       )




			def 							lowerCAmelCase__			(						self     :   List[Any]       )      ->BartTokenizer:



					'''simple docstring'''







					return BartTokenizer.from_pretrained(os.path.join(self.tmpdirname		,     "bart_tokenizer"       )       )




			def 							lowerCAmelCase__			(						self     :   List[str]       )      ->Dict:



					'''simple docstring'''







					shutil.rmtree(self.tmpdirname       )




			@require_tokenizers
			def 							lowerCAmelCase__			(						self     :   List[str]       )      ->Union[str, Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[int]	    =					os.path.join(self.tmpdirname		,     "rag_tokenizer"       )
					_UpperCAmelCase						:				str	    =					RagConfig(question_encoder=DPRConfig().to_dict()		,     generator=BartConfig().to_dict()       )
					_UpperCAmelCase						:				Optional[int]	    =					RagTokenizer(question_encoder=self.get_dpr_tokenizer()		,     generator=self.get_bart_tokenizer()       )
					rag_config.save_pretrained(lowerCamelCase__       )
					rag_tokenizer.save_pretrained(lowerCamelCase__       )
					_UpperCAmelCase						:				Dict	    =					RagTokenizer.from_pretrained(lowerCamelCase__		,     config=lowerCamelCase__       )
					self.assertIsInstance(new_rag_tokenizer.question_encoder		,     lowerCamelCase__       )
					self.assertEqual(new_rag_tokenizer.question_encoder.get_vocab()		,     rag_tokenizer.question_encoder.get_vocab()       )
					self.assertIsInstance(new_rag_tokenizer.generator		,     lowerCamelCase__       )
					self.assertEqual(new_rag_tokenizer.generator.get_vocab()		,     rag_tokenizer.generator.get_vocab()       )




			@slow
			def 							lowerCAmelCase__			(						self     :   List[str]       )      ->Optional[Any]:



					'''simple docstring'''







					_UpperCAmelCase						:				Union[str, Any]	    =					RagTokenizer.from_pretrained("facebook/rag-token-nq"       )
					_UpperCAmelCase						:				str	    =					[
					    "who got the first nobel prize in physics",
					    "when is the next deadpool movie being released",
					    "which mode is used for short wave broadcast service",
					    "who is the owner of reading football club",
					    "when is the next scandal episode coming out",
					    "when is the last time the philadelphia won the superbowl",
					    "what is the most current adobe flash player version",
					    "how many episodes are there in dragon ball z",
					    "what is the first step in the evolution of the eye",
					    "where is gall bladder situated in human body",
					    "what is the main mineral in lithium batteries",
					    "who is the president of usa right now",
					    "where do the greasers live in the outsiders",
					    "panda is a national animal of which country",
					    "what is the name of manchester united stadium",
					]
					_UpperCAmelCase						:				Optional[int]	    =					tokenizer(lowerCamelCase__       )
					self.assertIsNotNone(lowerCamelCase__       )






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



					'''simple docstring'''







					_UpperCAmelCase						:				Optional[Any]	    =					RagTokenizer.from_pretrained("facebook/rag-sequence-nq"       )
					_UpperCAmelCase						:				List[Any]	    =					[
					    "who got the first nobel prize in physics",
					    "when is the next deadpool movie being released",
					    "which mode is used for short wave broadcast service",
					    "who is the owner of reading football club",
					    "when is the next scandal episode coming out",
					    "when is the last time the philadelphia won the superbowl",
					    "what is the most current adobe flash player version",
					    "how many episodes are there in dragon ball z",
					    "what is the first step in the evolution of the eye",
					    "where is gall bladder situated in human body",
					    "what is the main mineral in lithium batteries",
					    "who is the president of usa right now",
					    "where do the greasers live in the outsiders",
					    "panda is a national animal of which country",
					    "what is the name of manchester united stadium",
					]
					_UpperCAmelCase						:				Optional[Any]	    =					tokenizer(lowerCamelCase__       )
					self.assertIsNotNone(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



