




"""simple docstring"""







import argparse
import glob
import logging
import os
from argparse import Namespace
from importlib import import_module

import numpy as np
import torch
from lightning_base import BaseTransformer, add_generic_args, generic_train
from seqeval.metrics import accuracy_score, fa_score, precision_score, recall_score
from torch.nn import CrossEntropyLoss
from torch.utils.data import DataLoader, TensorDataset
from utils_ner import TokenClassificationTask


a      =							logging.getLogger(__name__)






class       SCREAMING_SNAKE_CASE__					(					A_					):
						_a    						=						'''token-classification'''


						def __init__(							self				:			Optional[int]						,						lowerCAmelCase				:			Optional[int]					):
										if type(lowerCAmelCase					) == dict:
														lowerCAmelCase  =				Namespace(**lowerCAmelCase					)
										lowerCAmelCase  =				import_module("""tasks"""					)
										try:
														lowerCAmelCase  =				getattr(lowerCAmelCase						,						hparams.task_type					)
														lowerCAmelCase  =				token_classification_task_clazz()
										except AttributeError:
														raise ValueError(
														    f'''Task {hparams.task_type} needs to be defined as a TokenClassificationTask subclass in {module}. '''
														    f'''Available tasks classes are: {TokenClassificationTask.__subclasses__()}'''					)
										lowerCAmelCase  =				self.token_classification_task.get_labels(hparams.labels					)
										lowerCAmelCase  =				CrossEntropyLoss().ignore_index
										super().__init__(lowerCAmelCase						,						len(self.labels					)						,						self.mode					)


						def   __lowercase (							self				:			Tuple						,						**lowerCAmelCase				:			str					):
										return self.model(**lowerCAmelCase					)


						def   __lowercase (							self				:			str						,						lowerCAmelCase				:			str						,						lowerCAmelCase				:			List[str]					):
										lowerCAmelCase  =				{"""input_ids""": batch[0], """attention_mask""": batch[1], """labels""": batch[3]}
										if self.config.model_type != "distilbert":
														lowerCAmelCase  =				(
														    batch[2] if self.config.model_type in ["""bert""", """xlnet"""] else None
														)  # XLM and RoBERTa don"t use token_type_ids

										lowerCAmelCase  =				self(**lowerCAmelCase					)
										lowerCAmelCase  =				outputs[0]
										# tensorboard_logs = {"loss": loss, "rate": self.lr_scheduler.get_last_lr()[-1]}
										return {"loss": loss}


						def   __lowercase (							self				:			Tuple					):
										lowerCAmelCase  =				self.hparams
										for mode in ["train", "dev", "test"]:
														lowerCAmelCase  =				self._feature_file(lowerCAmelCase					)
														if os.path.exists(lowerCAmelCase					) and not args.overwrite_cache:
																		logger.info("""Loading features from cached file %s"""						,						lowerCAmelCase					)
																		lowerCAmelCase  =				torch.load(lowerCAmelCase					)
														else:
																		logger.info("""Creating features from dataset file at %s"""						,						args.data_dir					)
																		lowerCAmelCase  =				self.token_classification_task.read_examples_from_file(args.data_dir						,						lowerCAmelCase					)
																		lowerCAmelCase  =				self.token_classification_task.convert_examples_to_features(
																		    lowerCAmelCase						,						self.labels						,						args.max_seq_length						,						self.tokenizer						,						cls_token_at_end=bool(self.config.model_type in ["""xlnet"""]					)						,						cls_token=self.tokenizer.cls_token						,						cls_token_segment_id=2 if self.config.model_type in ["""xlnet"""] else 0						,						sep_token=self.tokenizer.sep_token						,						sep_token_extra=lowerCAmelCase						,						pad_on_left=bool(self.config.model_type in ["""xlnet"""]					)						,						pad_token=self.tokenizer.pad_token_id						,						pad_token_segment_id=self.tokenizer.pad_token_type_id						,						pad_token_label_id=self.pad_token_label_id						,						)
																		logger.info("""Saving features into cached file %s"""						,						lowerCAmelCase					)
																		torch.save(lowerCAmelCase						,						lowerCAmelCase					)


						def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			List[str]						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			Tuple = False					):
										lowerCAmelCase  =				self._feature_file(lowerCAmelCase					)
										logger.info("""Loading features from cached file %s"""						,						lowerCAmelCase					)
										lowerCAmelCase  =				torch.load(lowerCAmelCase					)
										lowerCAmelCase  =				torch.tensor([f.input_ids for f in features]						,						dtype=torch.long					)
										lowerCAmelCase  =				torch.tensor([f.attention_mask for f in features]						,						dtype=torch.long					)
										if features[0].token_type_ids is not None:
														lowerCAmelCase  =				torch.tensor([f.token_type_ids for f in features]						,						dtype=torch.long					)
										else:
														lowerCAmelCase  =				torch.tensor([0 for f in features]						,						dtype=torch.long					)
														# HACK(we will not use this anymore soon)
										lowerCAmelCase  =				torch.tensor([f.label_ids for f in features]						,						dtype=torch.long					)
										return DataLoader(
										    TensorDataset(lowerCAmelCase						,						lowerCAmelCase						,						lowerCAmelCase						,						lowerCAmelCase					)						,						batch_size=lowerCAmelCase					)


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Union[str, Any]						,						lowerCAmelCase				:			Tuple					):
										"""Compute validation""" ""
										lowerCAmelCase  =				{"""input_ids""": batch[0], """attention_mask""": batch[1], """labels""": batch[3]}
										if self.config.model_type != "distilbert":
														lowerCAmelCase  =				(
														    batch[2] if self.config.model_type in ["""bert""", """xlnet"""] else None
														)  # XLM and RoBERTa don"t use token_type_ids
										lowerCAmelCase  =				self(**lowerCAmelCase					)
										lowerCAmelCase  =				outputs[:2]
										lowerCAmelCase  =				logits.detach().cpu().numpy()
										lowerCAmelCase  =				inputs["""labels"""].detach().cpu().numpy()
										return {"val_loss": tmp_eval_loss.detach().cpu(), "pred": preds, "target": out_label_ids}


						def   __lowercase (							self				:			Any						,						lowerCAmelCase				:			Optional[Any]					):
										lowerCAmelCase  =				torch.stack([x["""val_loss"""] for x in outputs]					).mean()
										lowerCAmelCase  =				np.concatenate([x["""pred"""] for x in outputs]						,						axis=0					)
										lowerCAmelCase  =				np.argmax(lowerCAmelCase						,						axis=2					)
										lowerCAmelCase  =				np.concatenate([x["""target"""] for x in outputs]						,						axis=0					)

										lowerCAmelCase  =				dict(enumerate(self.labels					)					)
										lowerCAmelCase  =				[[] for _ in range(out_label_ids.shape[0]					)]
										lowerCAmelCase  =				[[] for _ in range(out_label_ids.shape[0]					)]

										for i in range(out_label_ids.shape[0]					):
														for j in range(out_label_ids.shape[1]					):
																		if out_label_ids[i, j] != self.pad_token_label_id:
																						out_label_list[i].append(label_map[out_label_ids[i][j]]					)
																						preds_list[i].append(label_map[preds[i][j]]					)

										lowerCAmelCase  =				{
										    """val_loss""": val_loss_mean,
										    """accuracy_score""": accuracy_score(lowerCAmelCase						,						lowerCAmelCase					),
										    """precision""": precision_score(lowerCAmelCase						,						lowerCAmelCase					),
										    """recall""": recall_score(lowerCAmelCase						,						lowerCAmelCase					),
										    """f1""": fa_score(lowerCAmelCase						,						lowerCAmelCase					),
										}

										lowerCAmelCase  =				dict(results.items()					)
										lowerCAmelCase  =				results
										return ret, preds_list, out_label_list


						def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			str					):
										# when stable
										lowerCAmelCase  =				self._eval_end(lowerCAmelCase					)
										lowerCAmelCase  =				ret["""log"""]
										return {"val_loss": logs["val_loss"], "log": logs, "progress_bar": logs}


						def   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			Union[str, Any]					):
										# updating to test_epoch_end instead of deprecated test_end
										lowerCAmelCase  =				self._eval_end(lowerCAmelCase					)

										# Converting to the dict required by pl
										# https://github.com/PyTorchLightning/pytorch-lightning/blob/master/\
										# pytorch_lightning/trainer/logging.py#L139
										lowerCAmelCase  =				ret["""log"""]
										# `val_loss` is the key returned by `self._eval_end()` but actually refers to `test_loss`
										return {"avg_test_loss": logs["val_loss"], "log": logs, "progress_bar": logs}




						@staticmethod
						def   __lowercase (							lowerCAmelCase				:			Union[str, Any]						,						lowerCAmelCase				:			Dict					):
										# Add NER specific options
										BaseTransformer.add_model_specific_args(lowerCAmelCase						,						lowerCAmelCase					)
										parser.add_argument(
										    """--task_type"""						,						default="""NER"""						,						type=lowerCAmelCase						,						help="""Task type to fine tune in training (e.g. NER, POS, etc)"""					)
										parser.add_argument(
										    """--max_seq_length"""						,						default=128						,						type=lowerCAmelCase						,						help=(
										        """The maximum total input sequence length after tokenization. Sequences longer """
										        """than this will be truncated, sequences shorter will be padded."""
										    )						,						)

										parser.add_argument(
										    """--labels"""						,						default=""""""						,						type=lowerCAmelCase						,						help="""Path to a file containing all labels. If not specified, CoNLL-2003 labels are used."""						,						)
										parser.add_argument(
										    """--gpus"""						,						default=0						,						type=lowerCAmelCase						,						help="""The number of GPUs allocated for this, it is by default 0 meaning none"""						,						)

										parser.add_argument(
										    """--overwrite_cache"""						,						action="""store_true"""						,						help="""Overwrite the cached training and evaluation sets"""					)

										return parser


if __name__ == "__main__":
						a      =							argparse.ArgumentParser()
						add_generic_args(parser, os.getcwd())
						a      =							NERTransformer.add_model_specific_args(parser, os.getcwd())
						a      =							parser.parse_args()
						a      =							NERTransformer(args)
						a      =							generic_train(model, args)

						if args.do_predict:
												# See https://github.com/huggingface/transformers/issues/3159
												# pl use this default format to create a checkpoint:
												# https://github.com/PyTorchLightning/pytorch-lightning/blob/master\
												# /pytorch_lightning/callbacks/model_checkpoint.py#L322
												a      =							sorted(glob.glob(os.path.join(args.output_dir, 'checkpoint-epoch=*.ckpt'), recursive=True))
												a      =							model.load_from_checkpoint(checkpoints[-1])
												trainer.test(model)











"""simple docstring"""







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






class       SCREAMING_SNAKE_CASE__					:


						def __init__(							self				:			Union[str, Any]					):
										lowerCAmelCase  =				{}


						def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			Union[str, Any]						,						lowerCAmelCase				:			Optional[Any]						,						lowerCAmelCase				:			Union[str, Any]=1					):
										if self.graph.get(lowerCAmelCase					):
														if self.graph[u].count([w, v]					) == 0:
																		self.graph[u].append([w, v]					)
										else:
														lowerCAmelCase  =				[[w, v]]
										if not self.graph.get(lowerCAmelCase					):
														lowerCAmelCase  =				[]


						def   __lowercase (							self				:			Optional[int]					):
										return list(self.graph					)


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			Optional[Any]						,						lowerCAmelCase				:			Dict					):
										if self.graph.get(lowerCAmelCase					):
														for _ in self.graph[u]:
																		if _[1] == v:
																						self.graph[u].remove(lowerCAmelCase					)


						def   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			Tuple=-2						,						lowerCAmelCase				:			List[Any]=-1					):
										if s == d:
														return []
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s

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

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

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


						def   __lowercase (							self				:			Tuple						,						lowerCAmelCase				:			Any=-1					):
										if c == -1:
														lowerCAmelCase  =				floor(random() * 1_0000					) + 10
										for i in range(lowerCAmelCase					):
														# every vertex has max 100 edges
														for _ in range(floor(random() * 102					) + 1					):
																		lowerCAmelCase  =				floor(random() * c					) + 1
																		if n != i:
																						self.add_pair(lowerCAmelCase						,						lowerCAmelCase						,						1					)


						def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			List[str]=-2					):
										lowerCAmelCase  =				deque()
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										d.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										while d:
														lowerCAmelCase  =				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   __lowercase (							self				:			List[Any]						,						lowerCAmelCase				:			Union[str, Any]					):
										lowerCAmelCase  =				0
										for x in self.graph:
														for y in self.graph[x]:
																		if y[1] == u:
																						count += 1
										return count


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			Tuple					):
										return len(self.graph[u]					)


						def   __lowercase (							self				:			Optional[int]						,						lowerCAmelCase				:			Optional[Any]=-2					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s
										lowerCAmelCase  =				[]

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

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

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


						def   __lowercase (							self				:			Any					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			Tuple					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			List[Any]						,						lowerCAmelCase				:			Any=-2						,						lowerCAmelCase				:			Tuple=-1					):
										lowerCAmelCase  =				time()
										self.dfs(lowerCAmelCase						,						lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin




						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			str=-2					):
										lowerCAmelCase  =				time()
										self.bfs(lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin






class       SCREAMING_SNAKE_CASE__					:


						def __init__(							self				:			int					):
										lowerCAmelCase  =				{}


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			Tuple						,						lowerCAmelCase				:			str						,						lowerCAmelCase				:			str=1					):
										# check if the u exists
										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
														lowerCAmelCase  =				[[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
														lowerCAmelCase  =				[[w, u]]


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Any						,						lowerCAmelCase				:			int					):
										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   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Optional[int]=-2						,						lowerCAmelCase				:			Optional[Any]=-1					):
										if s == d:
														return []
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				s

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

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

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


						def   __lowercase (							self				:			Any						,						lowerCAmelCase				:			Dict=-1					):
										if c == -1:
														lowerCAmelCase  =				floor(random() * 1_0000					) + 10
										for i in range(lowerCAmelCase					):
														# every vertex has max 100 edges
														for _ in range(floor(random() * 102					) + 1					):
																		lowerCAmelCase  =				floor(random() * c					) + 1
																		if n != i:
																						self.add_pair(lowerCAmelCase						,						lowerCAmelCase						,						1					)


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			Tuple=-2					):
										lowerCAmelCase  =				deque()
										lowerCAmelCase  =				[]
										if s == -2:
														lowerCAmelCase  =				list(self.graph					)[0]
										d.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										while d:
														lowerCAmelCase  =				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   __lowercase (							self				:			List[str]						,						lowerCAmelCase				:			str					):
										return len(self.graph[u]					)


						def   __lowercase (							self				:			Optional[Any]					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			int					):
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(self.graph					)[0]
										stack.append(lowerCAmelCase					)
										visited.append(lowerCAmelCase					)
										lowerCAmelCase  =				-2
										lowerCAmelCase  =				[]
										lowerCAmelCase  =				s
										lowerCAmelCase  =				False
										lowerCAmelCase  =				set()

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

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

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


						def   __lowercase (							self				:			str					):
										return list(self.graph					)


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			Dict=-2						,						lowerCAmelCase				:			List[str]=-1					):
										lowerCAmelCase  =				time()
										self.dfs(lowerCAmelCase						,						lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin




						def   __lowercase (							self				:			str						,						lowerCAmelCase				:			Union[str, Any]=-2					):
										lowerCAmelCase  =				time()
										self.bfs(lowerCAmelCase					)
										lowerCAmelCase  =				time()
										return end - begin





