
"""simple docstring"""


import unittest

from transformers import BertGenerationConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch

		from transformers import BertGenerationDecoder, BertGenerationEncoder







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      Optional[int]  ,A_     :      Any  ,A_     :      int=13  ,A_     :      Optional[int]=7  ,A_     :      List[Any]=True  ,A_     :      str=True  ,A_     :      Optional[Any]=99  ,A_     :      Optional[Any]=32  ,A_     :      Optional[int]=5  ,A_     :      str=4  ,A_     :      int=37  ,A_     :      Optional[Any]="gelu"  ,A_     :      int=0.1  ,A_     :      Dict=0.1  ,A_     :      Any=50  ,A_     :      Tuple=0.02  ,A_     :      Tuple=True  ,A_     :      Optional[Any]=None  ,)     ->   int:
							A						   =   parent
							A						   =   batch_size
							A						   =   seq_length
							A						   =   is_training
							A						   =   use_input_mask
							A						   =   vocab_size
							A						   =   hidden_size
							A						   =   num_hidden_layers
							A						   =   num_attention_heads
							A						   =   intermediate_size
							A						   =   hidden_act
							A						   =   hidden_dropout_prob
							A						   =   attention_probs_dropout_prob
							A						   =   max_position_embeddings
							A						   =   initializer_range
							A						   =   use_labels
							A						   =   scope


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[Any]:
							A						   =   ids_tensor([self.batch_size, self.seq_length]  ,self.vocab_size      )

							A						   =   None
							if self.use_input_mask:
								A						   =   random_attention_mask([self.batch_size, self.seq_length]      )

							if self.use_labels:
								A						   =   ids_tensor([self.batch_size, self.seq_length]  ,self.vocab_size      )

							A						   =   self.get_config()

							return config, input_ids, input_mask, token_labels


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   List[str]:
							return BertGenerationConfig(
							    vocab_size=self.vocab_size  ,hidden_size=self.hidden_size  ,num_hidden_layers=self.num_hidden_layers  ,num_attention_heads=self.num_attention_heads  ,intermediate_size=self.intermediate_size  ,hidden_act=self.hidden_act  ,hidden_dropout_prob=self.hidden_dropout_prob  ,attention_probs_dropout_prob=self.attention_probs_dropout_prob  ,max_position_embeddings=self.max_position_embeddings  ,is_decoder=A_  ,initializer_range=self.initializer_range  ,)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   Optional[int]:
							(
							    (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      
							)						   =   self.prepare_config_and_inputs()

							A						   =   True
							A						   =   floats_tensor([self.batch_size, self.seq_length, self.hidden_size]      )
							A						   =   ids_tensor([self.batch_size, self.seq_length]  ,vocab_size=2      )

							return (
							    config,
							    input_ids,
							    input_mask,
							    token_labels,
							    encoder_hidden_states,
							    encoder_attention_mask,
							)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      int  ,A_     :      Dict  ,A_     :      Any  ,A_     :      Union[str, Any]  ,**A_     :      int  ,)     ->   List[Any]:
							A						   =   BertGenerationEncoder(config=A_      )
							model.to(A_      )
							model.eval()
							A						   =   model(A_  ,attention_mask=A_      )
							A						   =   model(A_      )
							self.parent.assertEqual(result.last_hidden_state.shape  ,(self.batch_size, self.seq_length, self.hidden_size)      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,A_     :      str  ,A_     :      Union[str, Any]  ,A_     :      int  ,A_     :      Union[str, Any]  ,A_     :      Dict  ,A_     :      int  ,**A_     :      Union[str, Any]  ,)     ->   int:
							A						   =   True
							A						   =   BertGenerationEncoder(config=A_      )
							model.to(A_      )
							model.eval()
							A						   =   model(
							    A_  ,attention_mask=A_  ,encoder_hidden_states=A_  ,encoder_attention_mask=A_  ,)
							A						   =   model(
							    A_  ,attention_mask=A_  ,encoder_hidden_states=A_  ,)
							self.parent.assertEqual(result.last_hidden_state.shape  ,(self.batch_size, self.seq_length, self.hidden_size)      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      Union[str, Any]  ,A_     :      List[Any]  ,A_     :      Optional[Any]  ,A_     :      Any  ,A_     :      Optional[int]  ,A_     :      Dict  ,**A_     :      Tuple  ,)     ->   int:
							A						   =   True
							A						   =   True
							A						   =   BertGenerationDecoder(config=A_      ).to(A_      ).eval()

							# first forward pass
							A						   =   model(
							    A_  ,attention_mask=A_  ,encoder_hidden_states=A_  ,encoder_attention_mask=A_  ,use_cache=A_  ,)
							A						   =   outputs.past_key_values

							# create hypothetical multiple next token and extent to next_input_ids
							A						   =   ids_tensor((self.batch_size, 3)  ,config.vocab_size      )
							A						   =   ids_tensor((self.batch_size, 3)  ,vocab_size=2      )

							# append to next input_ids and
							A						   =   torch.cat([input_ids, next_tokens]  ,dim=-1      )
							A						   =   torch.cat([input_mask, next_mask]  ,dim=-1      )

							A						   =   model(
							    A_  ,attention_mask=A_  ,encoder_hidden_states=A_  ,encoder_attention_mask=A_  ,output_hidden_states=A_  ,)['hidden_states'][0]
							A						   =   model(
							    A_  ,attention_mask=A_  ,encoder_hidden_states=A_  ,encoder_attention_mask=A_  ,past_key_values=A_  ,output_hidden_states=A_  ,)['hidden_states'][0]

							# select random slice
							A						   =   ids_tensor((1,)  ,output_from_past.shape[-1]      ).item()
							A						   =   output_from_no_past[:, -3:, random_slice_idx].detach()
							A						   =   output_from_past[:, :, random_slice_idx].detach()

							self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]      )

							# test that outputs are equal for slice
							self.parent.assertTrue(torch.allclose(A_  ,A_  ,atol=1e-3      )      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      Optional[int]  ,A_     :      int  ,A_     :      int  ,A_     :      List[str]  ,*A_     :      int  ,)     ->   List[str]:
							A						   =   BertGenerationDecoder(A_      )
							model.to(A_      )
							model.eval()
							A						   =   model(A_  ,attention_mask=A_  ,labels=A_      )
							self.parent.assertEqual(result.logits.shape  ,(self.batch_size, self.seq_length, self.vocab_size)      )




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Dict:
							A   ,      A   ,      A   ,      A						   =   self.prepare_config_and_inputs()
							A						   =   {'input_ids': input_ids, 'attention_mask': input_mask}
							return config, inputs_dict







@require_torch
class 				lowerCAmelCase_				(      _lowercase		,					_lowercase		,					_lowercase		,					unittest.TestCase    ):



						'''simple docstring'''


						_lowerCamelCase:    str      =    (BertGenerationEncoder, BertGenerationDecoder) if is_torch_available() else ()
						_lowerCamelCase:    Optional[int]      =    (BertGenerationDecoder,) if is_torch_available() else ()
						_lowerCamelCase:    Union[str, Any]      =    (
						    {'''feature-extraction''': BertGenerationEncoder, '''text-generation''': BertGenerationDecoder}
						    if is_torch_available()
						    else {}
						)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							A						   =   BertGenerationEncoderTester(self      )
							A						   =   ConfigTester(self  ,config_class=A_  ,hidden_size=37      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							self.config_tester.run_common_tests()


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   Optional[Any]:
							A						   =   self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   int:
							A   ,      A   ,      A   ,      A						   =   self.model_tester.prepare_config_and_inputs()
							A						   =   'bert'
							self.model_tester.create_and_check_model(A_  ,A_  ,A_  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Optional[Any]:
							A						   =   self.model_tester.prepare_config_and_inputs_for_decoder()
							self.model_tester.create_and_check_model_as_decoder(*A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   str:
							A						   =   self.model_tester.prepare_config_and_inputs_for_decoder()
							self.model_tester.create_and_check_decoder_model_past_large_inputs(*A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   Dict:
							# This regression test was failing with PyTorch < 1.3
							(
							    (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      (
							    A
							)   ,      
							)						   =   self.model_tester.prepare_config_and_inputs_for_decoder()

							A						   =   None

							self.model_tester.create_and_check_model_as_decoder(
							    A_  ,A_  ,A_  ,A_  ,A_  ,A_  ,)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   List[str]:
							A						   =   self.model_tester.prepare_config_and_inputs_for_decoder()
							self.model_tester.create_and_check_for_causal_lm(*A_      )




						@slow
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   List[str]:
							A						   =   BertGenerationEncoder.from_pretrained('google/bert_for_seq_generation_L-24_bbc_encoder'      )
							self.assertIsNotNone(A_      )







@require_torch
class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						@slow
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Any:
							A						   =   BertGenerationEncoder.from_pretrained('google/bert_for_seq_generation_L-24_bbc_encoder'      )
							A						   =   torch.tensor([[101, 7592, 1010, 2026, 3899, 2003, 1_0140, 102]]      )
							with torch.no_grad():
								A						   =   model(A_      )[0]
							A						   =   torch.Size([1, 8, 1024]      )
							self.assertEqual(output.shape  ,A_      )
							A						   =   torch.tensor(
							    [[[0.17_75, 0.00_83, -0.03_21], [1.60_02, 0.12_87, 0.39_12], [2.14_73, 0.57_91, 0.60_66]]]      )
							self.assertTrue(torch.allclose(output[:, :3, :3]  ,A_  ,atol=1e-4      )      )







@require_torch
class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						@slow
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Tuple:
							A						   =   BertGenerationDecoder.from_pretrained('google/bert_for_seq_generation_L-24_bbc_encoder'      )
							A						   =   torch.tensor([[101, 7592, 1010, 2026, 3899, 2003, 1_0140, 102]]      )
							with torch.no_grad():
								A						   =   model(A_      )[0]
							A						   =   torch.Size([1, 8, 5_0358]      )
							self.assertEqual(output.shape  ,A_      )
							A						   =   torch.tensor(
							    [[[-0.57_88, -2.59_94, -3.70_54], [0.04_38, 4.79_97, 1.87_95], [1.58_62, 6.64_09, 4.46_38]]]      )
							self.assertTrue(torch.allclose(output[:, :3, :3]  ,A_  ,atol=1e-4      )      )

"""simple docstring"""


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







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      Dict      )     ->   int:
							A						   =   {}


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Union[str, Any]  ,A_     :      Any  ,A_     :      Optional[Any]=1      )     ->   int:
							if self.graph.get(A_      ):
								if self.graph[u].count([w, v]      ) == 0:
									self.graph[u].append([w, v]      )
							else:
								A						   =   [[w, v]]
							if not self.graph.get(A_      ):
								A						   =   []


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Optional[int]:
							return list(self.graph      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Union[str, Any]  ,A_     :      Dict      )     ->   Optional[Any]:
							if self.graph.get(A_      ):
								for _ in self.graph[u]:
									if _[1] == v:
										self.graph[u].remove(A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      int=-2  ,A_     :      Dict=-1      )     ->   str:
							if s == d:
								return []
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   s

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

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      Any=-1      )     ->   int:
							if c == -1:
								A						   =   floor(random() * 1_0000      ) + 10
							for i in range(A_      ):
								# every vertex has max 100 edges
								for _ in range(floor(random() * 102      ) + 1      ):
									A						   =   floor(random() * c      ) + 1
									if n != i:
										self.add_pair(A_  ,A_  ,1      )


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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,A_     :      Union[str, Any]      )     ->   str:
							return len(self.graph[u]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,A_     :      Union[str, Any]=-2      )     ->   Any:
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   s
							A						   =   []

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

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Tuple:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

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

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

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

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,A_     :      Tuple=-2  ,A_     :      List[str]=-1      )     ->   str:
							A						   =   time()
							self.dfs(A_  ,A_      )
							A						   =   time()
							return end - begin




						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]  ,A_     :      Union[str, Any]=-2      )     ->   Dict:
							A						   =   time()
							self.bfs(A_      )
							A						   =   time()
							return end - begin







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      List[Any]      )     ->   Tuple:
							A						   =   {}


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Optional[Any]  ,A_     :      str  ,A_     :      List[str]=1      )     ->   Dict:
							# check if the u exists
							if self.graph.get(A_      ):
								# 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						   =   [[w, v]]
							# add the other way
							if self.graph.get(A_      ):
								# 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						   =   [[w, u]]


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      List[Any]  ,A_     :      List[str]      )     ->   List[Any]:
							if self.graph.get(A_      ):
								for _ in self.graph[u]:
									if _[1] == v:
										self.graph[u].remove(A_      )
        # the other way round
							if self.graph.get(A_      ):
								for _ in self.graph[v]:
									if _[1] == u:
										self.graph[v].remove(A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      List[str]=-2  ,A_     :      List[Any]=-1      )     ->   int:
							if s == d:
								return []
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   s

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

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[int]=-1      )     ->   List[Any]:
							if c == -1:
								A						   =   floor(random() * 1_0000      ) + 10
							for i in range(A_      ):
								# every vertex has max 100 edges
								for _ in range(floor(random() * 102      ) + 1      ):
									A						   =   floor(random() * c      ) + 1
									if n != i:
										self.add_pair(A_  ,A_  ,1      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      Dict=-2      )     ->   List[Any]:
							A						   =   deque()
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							d.append(A_      )
							visited.append(A_      )
							while d:
								A						   =   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 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[Any]      )     ->   List[Any]:
							return len(self.graph[u]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   List[Any]:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

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

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   Any:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

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

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

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Any:
							return list(self.graph      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,A_     :      Optional[Any]=-2  ,A_     :      List[str]=-1      )     ->   Any:
							A						   =   time()
							self.dfs(A_  ,A_      )
							A						   =   time()
							return end - begin




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      List[Any]=-2      )     ->   Union[str, Any]:
							A						   =   time()
							self.bfs(A_      )
							A						   =   time()
							return end - begin