
"""simple docstring"""


import copy
import inspect
import unittest

from transformers import AutoBackbone
from transformers.configuration_utils import PretrainedConfig
from transformers.testing_utils import require_timm, require_torch, torch_device
from transformers.utils.import_utils import is_torch_available

from ...test_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor


if is_torch_available():
		import torch

		from transformers import TimmBackbone, TimmBackboneConfig

from ...test_pipeline_mixin import PipelineTesterMixin







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      Union[str, Any]  ,A_     :      Union[str, Any]  ,A_     :      Optional[int]=None  ,A_     :      List[Any]=None  ,A_     :      int=None  ,A_     :      Optional[int]="resnet50"  ,A_     :      Optional[Any]=3  ,A_     :      Any=32  ,A_     :      Any=3  ,A_     :      Tuple=True  ,A_     :      Union[str, Any]=True  ,)     ->   Dict:
							A						   =   parent
							A						   =   out_indices if out_indices is not None else [4]
							A						   =   stage_names
							A						   =   out_features
							A						   =   backbone
							A						   =   batch_size
							A						   =   image_size
							A						   =   num_channels
							A						   =   use_pretrained_backbone
							A						   =   is_training


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Union[str, Any]:
							A						   =   floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]      )
							A						   =   self.get_config()

							return config, pixel_values


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Union[str, Any]:
							return TimmBackboneConfig(
							    image_size=self.image_size  ,num_channels=self.num_channels  ,out_features=self.out_features  ,out_indices=self.out_indices  ,stage_names=self.stage_names  ,use_pretrained_backbone=self.use_pretrained_backbone  ,backbone=self.backbone  ,)


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      List[str]  ,A_     :      int      )     ->   List[str]:
							A						   =   TimmBackbone(config=A_      )
							model.to(A_      )
							model.eval()
							with torch.no_grad():
								A						   =   model(A_      )
							self.parent.assertEqual(
							    result.feature_map[-1].shape  ,(self.batch_size, model.channels[-1], 14, 14)  ,)




						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   Union[str, Any]:
							A						   =   self.prepare_config_and_inputs()
							A   ,      A						   =   config_and_inputs
							A						   =   {'pixel_values': pixel_values}
							return config, inputs_dict







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



						'''simple docstring'''


						_lowerCamelCase:    Optional[Any]      =    (TimmBackbone,) if is_torch_available() else ()
						_lowerCamelCase:    Union[str, Any]      =    {'''feature-extraction''': TimmBackbone} if is_torch_available() else {}
						_lowerCamelCase:    Union[str, Any]      =    False
						_lowerCamelCase:    str      =    False
						_lowerCamelCase:    Tuple      =    False
						_lowerCamelCase:    List[str]      =    False


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Union[str, Any]:
							A						   =   TimmBackboneModelTester(self      )
							A						   =   ConfigTester(self  ,config_class=A_  ,has_text_modality=A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Any:
							self.config_tester.create_and_test_config_to_json_string()
							self.config_tester.create_and_test_config_to_json_file()
							self.config_tester.create_and_test_config_from_and_save_pretrained()
							self.config_tester.create_and_test_config_with_num_labels()
							self.config_tester.check_config_can_be_init_without_params()
							self.config_tester.check_config_arguments_init()


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   List[Any]:
							A						   =   'resnet18'
							A						   =   'microsoft/resnet-18'

							A						   =   AutoBackbone.from_pretrained(A_  ,use_timm_backbone=A_      )
							A						   =   AutoBackbone.from_pretrained(A_      )

							self.assertEqual(len(timm_model.out_features      )  ,len(transformers_model.out_features      )      )
							self.assertEqual(len(timm_model.stage_names      )  ,len(transformers_model.stage_names      )      )
							self.assertEqual(timm_model.channels  ,transformers_model.channels      )
							# Out indices are set to the last layer by default. For timm models, we don't know
							# the number of layers in advance, so we set it to (-1,), whereas for transformers
							# models, we set it to [len(stage_names) - 1] (kept for backward compatibility).
							self.assertEqual(timm_model.out_indices  ,(-1,)      )
							self.assertEqual(transformers_model.out_indices  ,[len(timm_model.stage_names      ) - 1]      )

							A						   =   AutoBackbone.from_pretrained(A_  ,use_timm_backbone=A_  ,out_indices=[1, 2, 3]      )
							A						   =   AutoBackbone.from_pretrained(A_  ,out_indices=[1, 2, 3]      )

							self.assertEqual(timm_model.out_indices  ,transformers_model.out_indices      )
							self.assertEqual(len(timm_model.out_features      )  ,len(transformers_model.out_features      )      )
							self.assertEqual(timm_model.channels  ,transformers_model.channels      )


						@unittest.skip('TimmBackbone doesn\'t support feed forward chunking'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   str:
							pass


						@unittest.skip('TimmBackbone doesn\'t have num_hidden_layers attribute'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Dict:
							pass


						@unittest.skip('TimmBackbone initialization is managed on the timm side'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   int:
							pass


						@unittest.skip('TimmBackbone models doesn\'t have inputs_embeds'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   Dict:
							pass


						@unittest.skip('TimmBackbone models doesn\'t have inputs_embeds'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   Any:
							pass


						@unittest.skip('TimmBackbone model cannot be created without specifying a backbone checkpoint'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   List[Any]:
							pass


						@unittest.skip('Only checkpoints on timm can be loaded into TimmBackbone'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   str:
							pass


						@unittest.skip('model weights aren\'t tied in TimmBackbone.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   Any:
							pass


						@unittest.skip('model weights aren\'t tied in TimmBackbone.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							pass


						@unittest.skip('Only checkpoints on timm can be loaded into TimmBackbone'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   List[Any]:
							pass


						@unittest.skip('Only checkpoints on timm can be loaded into TimmBackbone'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Any:
							pass


						@unittest.skip('TimmBackbone doesn\'t have hidden size info in its configuration.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   Optional[int]:
							pass


						@unittest.skip('TimmBackbone doesn\'t support output_attentions.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[Any]:
							pass


						@unittest.skip('Safetensors is not supported by timm.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Optional[int]:
							pass


						@unittest.skip('Will be fixed soon by reducing the size of the model used for common tests.'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   str:
							pass


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   List[Any]:
							A   ,      A						   =   self.model_tester.prepare_config_and_inputs_for_common()

							for model_class in self.all_model_classes:
								A						   =   model_class(A_      )
								A						   =   inspect.signature(model.forward      )
								# signature.parameters is an OrderedDict => so arg_names order is deterministic
								A						   =   [*signature.parameters.keys()]

								A						   =   ['pixel_values']
								self.assertListEqual(arg_names[:1]  ,A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   str:
							A   ,      A						   =   self.model_tester.prepare_config_and_inputs_for_common()
							A						   =   True
							A						   =   self.has_attentions

							# no need to test all models as different heads yield the same functionality
							A						   =   self.all_model_classes[0]
							A						   =   model_class(A_      )
							model.to(A_      )

							A						   =   self._prepare_for_class(A_  ,A_      )
							A						   =   model(**A_      )
							A						   =   outputs[0][-1]

							# Encoder-/Decoder-only models
							A						   =   outputs.hidden_states[0]
							hidden_states.retain_grad()

							if self.has_attentions:
								A						   =   outputs.attentions[0]
								attentions.retain_grad()

							output.flatten()[0].backward(retain_graph=A_      )

							self.assertIsNotNone(hidden_states.grad      )

							if self.has_attentions:
								self.assertIsNotNone(attentions.grad      )




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   List[str]:
							A   ,      A						   =   self.model_tester.prepare_config_and_inputs_for_common()

							for model_class in self.all_model_classes:
								A						   =   model_class(A_      )
								model.to(A_      )
								model.eval()
								A						   =   model(**A_      )

								self.assertEqual(len(result.feature_maps      )  ,len(config.out_indices      )      )
								self.assertEqual(len(model.channels      )  ,len(config.out_indices      )      )

								# Check output of last stage is taken if out_features=None, out_indices=None
								A						   =   copy.deepcopy(A_      )
								A						   =   None
								A						   =   model_class(A_      )
								model.to(A_      )
								model.eval()
								A						   =   model(**A_      )

								self.assertEqual(len(result.feature_maps      )  ,1      )
								self.assertEqual(len(model.channels      )  ,1      )

								# Check backbone can be initialized with fresh weights
								A						   =   copy.deepcopy(A_      )
								A						   =   False
								A						   =   model_class(A_      )
								model.to(A_      )
								model.eval()
								A						   =   model(**A_      )

"""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