




"""simple docstring"""

import json
import os
import pickle
import shutil
import tempfile
from unittest import TestCase
from unittest.mock import patch

import numpy as np
from datasets import Dataset

from transformers import is_faiss_available
from transformers.models.bart.configuration_bart import BartConfig
from transformers.models.bart.tokenization_bart import BartTokenizer
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.dpr.tokenization_dpr import DPRContextEncoderTokenizer, DPRQuestionEncoderTokenizer
from transformers.models.rag.configuration_rag import RagConfig
from transformers.models.rag.retrieval_rag import CustomHFIndex, RagRetriever
from transformers.models.roberta.tokenization_roberta import VOCAB_FILES_NAMES as BART_VOCAB_FILES_NAMES
from transformers.testing_utils import require_faiss, require_sentencepiece, require_tokenizers, require_torch


if is_faiss_available():
		import faiss

@require_faiss
class        lowercase      (    __UpperCAmelCase):







				def 					a_  (							self   :					Optional[Any]       ):



					"""simple docstring"""

					A_  :				Optional[Any]	   =		tempfile.mkdtemp()
					A_  :				List[str]	   =		8

					# DPR tok
					A_  :				Optional[int]	   =		[
					    '''[UNK]''',
					    '''[CLS]''',
					    '''[SEP]''',
					    '''[PAD]''',
					    '''[MASK]''',
					    '''want''',
					    '''##want''',
					    '''##ed''',
					    '''wa''',
					    '''un''',
					    '''runn''',
					    '''##ing''',
					    ''',''',
					    '''low''',
					    '''lowest''',
					]
					A_  :				Optional[Any]	   =		os.path.join(self.tmpdirname      ,     '''dpr_tokenizer'''       )
					os.makedirs(_lowerCamelCase      ,     exist_ok=_lowerCamelCase       )
					A_  :				Optional[Any]	   =		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
					A_  :				Optional[int]	   =		[
					    '''l''',
					    '''o''',
					    '''w''',
					    '''e''',
					    '''r''',
					    '''s''',
					    '''t''',
					    '''i''',
					    '''d''',
					    '''n''',
					    '''\u0120''',
					    '''\u0120l''',
					    '''\u0120n''',
					    '''\u0120lo''',
					    '''\u0120low''',
					    '''er''',
					    '''\u0120lowest''',
					    '''\u0120newer''',
					    '''\u0120wider''',
					    '''<unk>''',
					]
					A_  :				Dict	   =		dict(zip(_lowerCamelCase      ,     range(len(_lowerCamelCase       )       )       )       )
					A_  :				int	   =		['''#version: 0.2''', '''\u0120 l''', '''\u0120l o''', '''\u0120lo w''', '''e r''', '''''']
					A_  :				Optional[Any]	   =		{'''unk_token''': '''<unk>'''}

					A_  :				Union[str, Any]	   =		os.path.join(self.tmpdirname      ,     '''bart_tokenizer'''       )
					os.makedirs(_lowerCamelCase      ,     exist_ok=_lowerCamelCase       )
					A_  :				Union[str, Any]	   =		os.path.join(_lowerCamelCase      ,     BART_VOCAB_FILES_NAMES['''vocab_file''']       )
					A_  :				List[str]	   =		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 					a_  (							self   :					Any       ):



					"""simple docstring"""

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







				def 					a_  (							self   :					Optional[Any]       ):



					"""simple docstring"""

					return DPRContextEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname      ,     '''dpr_tokenizer'''       )       )







				def 					a_  (							self   :					int       ):



					"""simple docstring"""

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







				def 					a_  (							self   :					List[str]       ):



					"""simple docstring"""

					shutil.rmtree(self.tmpdirname       )







				def 					a_  (							self   :					Tuple       ):



					"""simple docstring"""

					A_  :				List[str]	   =		Dataset.from_dict(
					    {
					        '''id''': ['''0''', '''1'''],
					        '''text''': ['''foo''', '''bar'''],
					        '''title''': ['''Foo''', '''Bar'''],
					        '''embeddings''': [np.ones(self.retrieval_vector_size       ), 2 * np.ones(self.retrieval_vector_size       )],
					    }       )
					dataset.add_faiss_index('''embeddings'''      ,     string_factory='''Flat'''      ,     metric_type=faiss.METRIC_INNER_PRODUCT       )
					return dataset







				def 					a_  (							self   :					Optional[int]       ):



					"""simple docstring"""

					A_  :				Optional[int]	   =		self.get_dummy_dataset()
					A_  :				int	   =		RagConfig(
					    retrieval_vector_size=self.retrieval_vector_size      ,     question_encoder=DPRConfig().to_dict()      ,     generator=BartConfig().to_dict()      ,     )
					with patch('''transformers.models.rag.retrieval_rag.load_dataset'''       ) as mock_load_dataset:
						A_  :				Any	   =		dataset
						A_  :				List[Any]	   =		RagRetriever(
						    _lowerCamelCase      ,     question_encoder_tokenizer=self.get_dpr_tokenizer()      ,     generator_tokenizer=self.get_bart_tokenizer()      ,     )
					return retriever







				def 					a_  (							self   :					List[str]      ,     _lowerCamelCase   :					bool       ):



					"""simple docstring"""

					A_  :				Union[str, Any]	   =		self.get_dummy_dataset()
					A_  :				List[str]	   =		RagConfig(
					    retrieval_vector_size=self.retrieval_vector_size      ,     question_encoder=DPRConfig().to_dict()      ,     generator=BartConfig().to_dict()      ,     index_name='''custom'''      ,     )
					if from_disk:
						A_  :				List[str]	   =		os.path.join(self.tmpdirname      ,     '''dataset'''       )
						A_  :				str	   =		os.path.join(self.tmpdirname      ,     '''index.faiss'''       )
						dataset.get_index('''embeddings'''       ).save(os.path.join(self.tmpdirname      ,     '''index.faiss'''       )       )
						dataset.drop_index('''embeddings'''       )
						dataset.save_to_disk(os.path.join(self.tmpdirname      ,     '''dataset'''       )       )
						del dataset
						A_  :				Dict	   =		RagRetriever(
						    _lowerCamelCase      ,     question_encoder_tokenizer=self.get_dpr_tokenizer()      ,     generator_tokenizer=self.get_bart_tokenizer()      ,     )
					else:
						A_  :				Any	   =		RagRetriever(
						    _lowerCamelCase      ,     question_encoder_tokenizer=self.get_dpr_tokenizer()      ,     generator_tokenizer=self.get_bart_tokenizer()      ,     index=CustomHFIndex(config.retrieval_vector_size      ,     _lowerCamelCase       )      ,     )
					return retriever







				def 					a_  (							self   :					Union[str, Any]       ):



					"""simple docstring"""

					A_  :				str	   =		Dataset.from_dict(
					    {
					        '''id''': ['''0''', '''1'''],
					        '''text''': ['''foo''', '''bar'''],
					        '''title''': ['''Foo''', '''Bar'''],
					        '''embeddings''': [np.ones(self.retrieval_vector_size + 1       ), 2 * np.ones(self.retrieval_vector_size + 1       )],
					    }       )
					dataset.add_faiss_index('''embeddings'''      ,     string_factory='''Flat'''      ,     metric_type=faiss.METRIC_INNER_PRODUCT       )

					A_  :				Optional[int]	   =		os.path.join(self.tmpdirname      ,     '''hf_bert_base.hnswSQ8_correct_phi_128.c_index'''       )
					dataset.save_faiss_index('''embeddings'''      ,     index_file_name + '''.index.dpr'''       )
					pickle.dump(dataset['''id''']      ,     open(index_file_name + '''.index_meta.dpr'''      ,     '''wb'''       )       )

					A_  :				int	   =		os.path.join(self.tmpdirname      ,     '''psgs_w100.tsv.pkl'''       )
					A_  :				Union[str, Any]	   =		{sample['''id''']: [sample['''text'''], sample['''title''']] for sample in dataset}
					pickle.dump(_lowerCamelCase      ,     open(_lowerCamelCase      ,     '''wb'''       )       )

					A_  :				int	   =		RagConfig(
					    retrieval_vector_size=self.retrieval_vector_size      ,     question_encoder=DPRConfig().to_dict()      ,     generator=BartConfig().to_dict()      ,     index_name='''legacy'''      ,     index_path=self.tmpdirname      ,     )
					A_  :				List[str]	   =		RagRetriever(
					    _lowerCamelCase      ,     question_encoder_tokenizer=self.get_dpr_tokenizer()      ,     generator_tokenizer=self.get_bart_tokenizer()       )
					return retriever







				def 					a_  (							self   :					Optional[int]       ):



					"""simple docstring"""

					A_  :				Tuple	   =		1
					A_  :				Optional[Any]	   =		self.get_dummy_canonical_hf_index_retriever()
					A_  :				List[str]	   =		np.array(
					    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
					A_   , A_   , A_  :				List[str]	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=_lowerCamelCase       )
					self.assertEqual(retrieved_doc_embeds.shape      ,     (2, n_docs, self.retrieval_vector_size)       )
					self.assertEqual(len(_lowerCamelCase       )      ,     2       )
					self.assertEqual(sorted(doc_dicts[0]       )      ,     ['''embeddings''', '''id''', '''text''', '''title''']       )
					self.assertEqual(len(doc_dicts[0]['''id''']       )      ,     _lowerCamelCase       )
					self.assertEqual(doc_dicts[0]['''id'''][0]      ,     '''1'''       )  # max inner product is reached with second doc
					self.assertEqual(doc_dicts[1]['''id'''][0]      ,     '''0'''       )  # max inner product is reached with first doc
					self.assertListEqual(doc_ids.tolist()      ,     [[1], [0]]       )







				def 					a_  (							self   :					List[str]       ):



					"""simple docstring"""

					A_  :				Dict	   =		self.get_dummy_canonical_hf_index_retriever()
					with tempfile.TemporaryDirectory() as tmp_dirname:
						with patch('''transformers.models.rag.retrieval_rag.load_dataset'''       ) as mock_load_dataset:
							A_  :				Dict	   =		self.get_dummy_dataset()
							retriever.save_pretrained(_lowerCamelCase       )
							A_  :				Any	   =		RagRetriever.from_pretrained(_lowerCamelCase       )
							self.assertIsInstance(_lowerCamelCase      ,     _lowerCamelCase       )
							A_  :				Union[str, Any]	   =		np.array(
							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
							A_  :				Dict	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=1       )
							self.assertTrue(out is not None       )







				def 					a_  (							self   :					Tuple       ):



					"""simple docstring"""

					A_  :				Any	   =		1
					A_  :				Union[str, Any]	   =		self.get_dummy_custom_hf_index_retriever(from_disk=_lowerCamelCase       )
					A_  :				Optional[int]	   =		np.array(
					    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
					A_   , A_   , A_  :				List[str]	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=_lowerCamelCase       )
					self.assertEqual(retrieved_doc_embeds.shape      ,     (2, n_docs, self.retrieval_vector_size)       )
					self.assertEqual(len(_lowerCamelCase       )      ,     2       )
					self.assertEqual(sorted(doc_dicts[0]       )      ,     ['''embeddings''', '''id''', '''text''', '''title''']       )
					self.assertEqual(len(doc_dicts[0]['''id''']       )      ,     _lowerCamelCase       )
					self.assertEqual(doc_dicts[0]['''id'''][0]      ,     '''1'''       )  # max inner product is reached with second doc
					self.assertEqual(doc_dicts[1]['''id'''][0]      ,     '''0'''       )  # max inner product is reached with first doc
					self.assertListEqual(doc_ids.tolist()      ,     [[1], [0]]       )







				def 					a_  (							self   :					Dict       ):



					"""simple docstring"""

					A_  :				Dict	   =		self.get_dummy_custom_hf_index_retriever(from_disk=_lowerCamelCase       )
					with tempfile.TemporaryDirectory() as tmp_dirname:
						retriever.save_pretrained(_lowerCamelCase       )
						A_  :				str	   =		RagRetriever.from_pretrained(_lowerCamelCase       )
						self.assertIsInstance(_lowerCamelCase      ,     _lowerCamelCase       )
						A_  :				int	   =		np.array(
						    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
						A_  :				Optional[Any]	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=1       )
						self.assertTrue(out is not None       )







				def 					a_  (							self   :					str       ):



					"""simple docstring"""

					A_  :				List[str]	   =		1
					A_  :				Dict	   =		self.get_dummy_custom_hf_index_retriever(from_disk=_lowerCamelCase       )
					A_  :				Optional[Any]	   =		np.array(
					    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
					A_   , A_   , A_  :				Optional[int]	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=_lowerCamelCase       )
					self.assertEqual(retrieved_doc_embeds.shape      ,     (2, n_docs, self.retrieval_vector_size)       )
					self.assertEqual(len(_lowerCamelCase       )      ,     2       )
					self.assertEqual(sorted(doc_dicts[0]       )      ,     ['''embeddings''', '''id''', '''text''', '''title''']       )
					self.assertEqual(len(doc_dicts[0]['''id''']       )      ,     _lowerCamelCase       )
					self.assertEqual(doc_dicts[0]['''id'''][0]      ,     '''1'''       )  # max inner product is reached with second doc
					self.assertEqual(doc_dicts[1]['''id'''][0]      ,     '''0'''       )  # max inner product is reached with first doc
					self.assertListEqual(doc_ids.tolist()      ,     [[1], [0]]       )







				def 					a_  (							self   :					Tuple       ):



					"""simple docstring"""

					A_  :				Optional[int]	   =		self.get_dummy_custom_hf_index_retriever(from_disk=_lowerCamelCase       )
					with tempfile.TemporaryDirectory() as tmp_dirname:
						retriever.save_pretrained(_lowerCamelCase       )
						A_  :				str	   =		RagRetriever.from_pretrained(_lowerCamelCase       )
						self.assertIsInstance(_lowerCamelCase      ,     _lowerCamelCase       )
						A_  :				List[Any]	   =		np.array(
						    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
						A_  :				Tuple	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=1       )
						self.assertTrue(out is not None       )







				def 					a_  (							self   :					Dict       ):



					"""simple docstring"""

					A_  :				Tuple	   =		1
					A_  :				int	   =		self.get_dummy_legacy_index_retriever()
					A_  :				Optional[int]	   =		np.array(
					    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
					A_   , A_   , A_  :				Optional[int]	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=_lowerCamelCase       )
					self.assertEqual(retrieved_doc_embeds.shape      ,     (2, n_docs, self.retrieval_vector_size)       )
					self.assertEqual(len(_lowerCamelCase       )      ,     2       )
					self.assertEqual(sorted(doc_dicts[0]       )      ,     ['''text''', '''title''']       )
					self.assertEqual(len(doc_dicts[0]['''text''']       )      ,     _lowerCamelCase       )
					self.assertEqual(doc_dicts[0]['''text'''][0]      ,     '''bar'''       )  # max inner product is reached with second doc
					self.assertEqual(doc_dicts[1]['''text'''][0]      ,     '''foo'''       )  # max inner product is reached with first doc
					self.assertListEqual(doc_ids.tolist()      ,     [[1], [0]]       )







				def 					a_  (							self   :					str       ):



					"""simple docstring"""

					A_  :				Union[str, Any]	   =		self.get_dummy_legacy_index_retriever()
					with tempfile.TemporaryDirectory() as tmp_dirname:
						retriever.save_pretrained(_lowerCamelCase       )
						A_  :				str	   =		RagRetriever.from_pretrained(_lowerCamelCase       )
						self.assertIsInstance(_lowerCamelCase      ,     _lowerCamelCase       )
						A_  :				str	   =		np.array(
						    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
						A_  :				Any	   =		retriever.retrieve(_lowerCamelCase      ,     n_docs=1       )
						self.assertTrue(out is not None       )







				@require_torch
				@require_tokenizers
				@require_sentencepiece
				def 					a_  (							self   :					Any       ):



					"""simple docstring"""

					import torch

					A_  :				List[str]	   =		1
					A_  :				int	   =		self.get_dummy_canonical_hf_index_retriever()
					A_  :				int	   =		[[5, 7], [10, 11]]
					A_  :				Union[str, Any]	   =		np.array(
					    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
					A_  :				Optional[Any]	   =		retriever(_lowerCamelCase      ,     _lowerCamelCase      ,     prefix=retriever.config.generator.prefix      ,     n_docs=_lowerCamelCase       )
					A_   , A_   , A_  :				Optional[int]	   =		(
					    out['''context_input_ids'''],
					    out['''context_attention_mask'''],
					    out['''retrieved_doc_embeds'''],
					)
					self.assertEqual(retrieved_doc_embeds.shape      ,     (2, n_docs, self.retrieval_vector_size)       )
					self.assertIsInstance(_lowerCamelCase      ,     _lowerCamelCase       )
					self.assertIsInstance(_lowerCamelCase      ,     _lowerCamelCase       )
					self.assertIsInstance(_lowerCamelCase      ,     np.ndarray       )

					A_  :				Optional[int]	   =		retriever(
					    _lowerCamelCase      ,     _lowerCamelCase      ,     prefix=retriever.config.generator.prefix      ,     n_docs=_lowerCamelCase      ,     return_tensors='''pt'''      ,     )
					A_   , A_   , A_   , A_  :				Union[str, Any]	   =		(  # noqa: F841
					    out['''context_input_ids'''],
					    out['''context_attention_mask'''],
					    out['''retrieved_doc_embeds'''],
					    out['''doc_ids'''],
					)
					self.assertEqual(retrieved_doc_embeds.shape      ,     (2, n_docs, self.retrieval_vector_size)       )
					self.assertIsInstance(_lowerCamelCase      ,     torch.Tensor       )
					self.assertIsInstance(_lowerCamelCase      ,     torch.Tensor       )
					self.assertIsInstance(_lowerCamelCase      ,     torch.Tensor       )







				@require_torch
				@require_tokenizers
				@require_sentencepiece
				def 					a_  (							self   :					Optional[Any]       ):



					"""simple docstring"""

					A_  :				Dict	   =		self.get_dpr_ctx_encoder_tokenizer()
					A_  :				List[str]	   =		1
					A_  :				str	   =		self.get_dummy_custom_hf_index_retriever(from_disk=_lowerCamelCase       )
					retriever.set_ctx_encoder_tokenizer(_lowerCamelCase       )

					A_  :				Optional[Any]	   =		[[5, 7], [10, 11]]
					A_  :				Union[str, Any]	   =		np.array(
					    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]      ,     dtype=np.floataa       )
					A_  :				int	   =		retriever(_lowerCamelCase      ,     _lowerCamelCase      ,     prefix=retriever.config.generator.prefix      ,     n_docs=_lowerCamelCase       )

					self.assertEqual(
					    len(_lowerCamelCase       )      ,     6       )  # check whether the retriever output consist of 6 attributes including tokenized docs
					self.assertEqual(
					    all(k in out for k in ('''tokenized_doc_ids''', '''tokenized_doc_attention_mask''')       )      ,     _lowerCamelCase       )  # check for doc token related keys in dictionary.











"""simple docstring"""

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

class        lowercase      :







				def __init__(							self   :					Dict       ):



					"""simple docstring"""

					A_  :				Tuple	   =		{}







				def 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					List[Any]      ,     _lowerCamelCase   :					Dict      ,     _lowerCamelCase   :					List[Any]=1       ):



					"""simple docstring"""

					if self.graph.get(_lowerCamelCase       ):
						if self.graph[u].count([w, v]       ) == 0:
							self.graph[u].append([w, v]       )
					else:
						A_  :				int	   =		[[w, v]]
					if not self.graph.get(_lowerCamelCase       ):
						A_  :				List[Any]	   =		[]







				def 					a_  (							self   :					Optional[int]       ):



					"""simple docstring"""

					return list(self.graph       )







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					str      ,     _lowerCamelCase   :					Tuple       ):



					"""simple docstring"""

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







				def 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					Optional[int]=-2      ,     _lowerCamelCase   :					Tuple=-1       ):



					"""simple docstring"""

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

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				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]       )
										A_  :				Union[str, Any]	   =		node[1]
										break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							if len(_lowerCamelCase       ) != 0:
								A_  :				Optional[int]	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				List[Any]	   =		ss

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







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					List[Any]=-1       ):



					"""simple docstring"""

					if c == -1:
						A_  :				List[Any]	   =		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       ):
							A_  :				Tuple	   =		floor(random() * c       ) + 1
							if n != i:
								self.add_pair(_lowerCamelCase      ,     _lowerCamelCase      ,     1       )







				def 					a_  (							self   :					Optional[int]      ,     _lowerCamelCase   :					Union[str, Any]=-2       ):



					"""simple docstring"""

					A_  :				List[str]	   =		deque()
					A_  :				int	   =		[]
					if s == -2:
						A_  :				Any	   =		list(self.graph       )[0]
					d.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					while d:
						A_  :				List[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 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					Tuple       ):



					"""simple docstring"""

					A_  :				List[Any]	   =		0
					for x in self.graph:
						for y in self.graph[x]:
							if y[1] == u:
								count += 1
					return count







				def 					a_  (							self   :					Any      ,     _lowerCamelCase   :					Optional[Any]       ):



					"""simple docstring"""

					return len(self.graph[u]       )







				def 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					Tuple=-2       ):



					"""simple docstring"""

					A_  :				int	   =		[]
					A_  :				Optional[Any]	   =		[]
					if s == -2:
						A_  :				List[str]	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				str	   =		s
					A_  :				List[Any]	   =		[]

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

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

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







				def 					a_  (							self   :					Dict       ):



					"""simple docstring"""

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

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Dict	   =		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
								):
									A_  :				Tuple	   =		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]       )
									A_  :				int	   =		node[1]
									break

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

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







				def 					a_  (							self   :					List[str]       ):



					"""simple docstring"""

					A_  :				Dict	   =		[]
					A_  :				Dict	   =		[]
					A_  :				Optional[Any]	   =		list(self.graph       )[0]
					stack.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					A_  :				Optional[Any]	   =		-2
					A_  :				List[str]	   =		[]
					A_  :				List[Any]	   =		s
					A_  :				int	   =		False
					A_  :				Any	   =		set()

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				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
								):
									A_  :				Dict	   =		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]       )
									A_  :				Any	   =		node[1]
									break

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

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







				def 					a_  (							self   :					Tuple      ,     _lowerCamelCase   :					Union[str, Any]=-2      ,     _lowerCamelCase   :					int=-1       ):



					"""simple docstring"""

					A_  :				int	   =		time()
					self.dfs(_lowerCamelCase      ,     _lowerCamelCase       )
					A_  :				int	   =		time()
					return end - begin







				def 					a_  (							self   :					Optional[Any]      ,     _lowerCamelCase   :					str=-2       ):



					"""simple docstring"""

					A_  :				int	   =		time()
					self.bfs(_lowerCamelCase       )
					A_  :				Union[str, Any]	   =		time()
					return end - begin

class        lowercase      :







				def __init__(							self   :					Any       ):



					"""simple docstring"""

					A_  :				Tuple	   =		{}







				def 					a_  (							self   :					List[Any]      ,     _lowerCamelCase   :					Optional[Any]      ,     _lowerCamelCase   :					Optional[Any]      ,     _lowerCamelCase   :					Optional[int]=1       ):



					"""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
						A_  :				Union[str, Any]	   =		[[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
						A_  :				Tuple	   =		[[w, u]]







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					Optional[Any]      ,     _lowerCamelCase   :					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 					a_  (							self   :					Any      ,     _lowerCamelCase   :					str=-2      ,     _lowerCamelCase   :					int=-1       ):



					"""simple docstring"""

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

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				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]       )
										A_  :				int	   =		node[1]
										break

            # check if all the children are visited
						if s == ss:
							stack.pop()
							if len(_lowerCamelCase       ) != 0:
								A_  :				List[Any]	   =		stack[len(_lowerCamelCase       ) - 1]
						else:
							A_  :				str	   =		ss

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







				def 					a_  (							self   :					Optional[Any]      ,     _lowerCamelCase   :					Union[str, Any]=-1       ):



					"""simple docstring"""

					if c == -1:
						A_  :				List[Any]	   =		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       ):
							A_  :				List[str]	   =		floor(random() * c       ) + 1
							if n != i:
								self.add_pair(_lowerCamelCase      ,     _lowerCamelCase      ,     1       )







				def 					a_  (							self   :					Dict      ,     _lowerCamelCase   :					List[Any]=-2       ):



					"""simple docstring"""

					A_  :				Dict	   =		deque()
					A_  :				Tuple	   =		[]
					if s == -2:
						A_  :				List[str]	   =		list(self.graph       )[0]
					d.append(_lowerCamelCase       )
					visited.append(_lowerCamelCase       )
					while d:
						A_  :				str	   =		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 					a_  (							self   :					Any      ,     _lowerCamelCase   :					int       ):



					"""simple docstring"""

					return len(self.graph[u]       )







				def 					a_  (							self   :					Any       ):



					"""simple docstring"""

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

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				Tuple	   =		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
								):
									A_  :				Tuple	   =		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]       )
									A_  :				str	   =		node[1]
									break

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

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







				def 					a_  (							self   :					Union[str, Any]       ):



					"""simple docstring"""

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

					while True:
						# check if there is any non isolated nodes
						if len(self.graph[s]       ) != 0:
							A_  :				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
								):
									A_  :				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]       )
									A_  :				Optional[Any]	   =		node[1]
									break

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

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







				def 					a_  (							self   :					Union[str, Any]       ):



					"""simple docstring"""

					return list(self.graph       )







				def 					a_  (							self   :					Tuple      ,     _lowerCamelCase   :					Union[str, Any]=-2      ,     _lowerCamelCase   :					str=-1       ):



					"""simple docstring"""

					A_  :				Optional[int]	   =		time()
					self.dfs(_lowerCamelCase      ,     _lowerCamelCase       )
					A_  :				Union[str, Any]	   =		time()
					return end - begin







				def 					a_  (							self   :					Tuple      ,     _lowerCamelCase   :					str=-2       ):



					"""simple docstring"""

					A_  :				Optional[int]	   =		time()
					self.bfs(_lowerCamelCase       )
					A_  :				List[str]	   =		time()
					return end - begin





