




"""simple docstring"""

import inspect
import unittest

from transformers import MobileNetVaConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
  import torch

  from transformers import MobileNetVaForImageClassification, MobileNetVaModel
  from transformers.models.mobilenet_va.modeling_mobilenet_va import MOBILENET_V1_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
  from PIL import Image

  from transformers import MobileNetVaImageProcessor

class        lowercase      (    lowerCAmelCase__):







    def 					a_  (							self   :					Optional[int]       ):



     """simple docstring"""

     A_  :				List[str]	   =		self.config_class(**self.inputs_dict       )
     self.parent.assertTrue(hasattr(_lowerCamelCase      ,     '''tf_padding'''       )       )
     self.parent.assertTrue(hasattr(_lowerCamelCase      ,     '''depth_multiplier'''       )       )

class        lowercase      :







    def __init__(							self   :					str      ,     _lowerCamelCase   :					Tuple      ,     _lowerCamelCase   :					str=13      ,     _lowerCamelCase   :					List[str]=3      ,     _lowerCamelCase   :					Dict=32      ,     _lowerCamelCase   :					Any=0.25      ,     _lowerCamelCase   :					List[str]=8      ,     _lowerCamelCase   :					str=True      ,     _lowerCamelCase   :					Optional[Any]=10_24      ,     _lowerCamelCase   :					int=32      ,     _lowerCamelCase   :					Any="relu6"      ,     _lowerCamelCase   :					Union[str, Any]=0.1      ,     _lowerCamelCase   :					str=0.02      ,     _lowerCamelCase   :					List[Any]=True      ,     _lowerCamelCase   :					List[str]=True      ,     _lowerCamelCase   :					List[str]=10      ,     _lowerCamelCase   :					Tuple=None      ,     ):



     """simple docstring"""

     A_  :				Dict	   =		parent
     A_  :				Union[str, Any]	   =		batch_size
     A_  :				Optional[Any]	   =		num_channels
     A_  :				Union[str, Any]	   =		image_size
     A_  :				List[str]	   =		depth_multiplier
     A_  :				int	   =		min_depth
     A_  :				List[Any]	   =		tf_padding
     A_  :				Optional[Any]	   =		int(last_hidden_size * depth_multiplier       )
     A_  :				Tuple	   =		output_stride
     A_  :				str	   =		hidden_act
     A_  :				str	   =		classifier_dropout_prob
     A_  :				List[Any]	   =		use_labels
     A_  :				Union[str, Any]	   =		is_training
     A_  :				Optional[Any]	   =		num_labels
     A_  :				List[Any]	   =		initializer_range
     A_  :				Optional[int]	   =		scope







    def 					a_  (							self   :					Any       ):



     """simple docstring"""

     A_  :				int	   =		floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]       )

     A_  :				Any	   =		None
     A_  :				Optional[int]	   =		None
     if self.use_labels:
      A_  :				Union[str, Any]	   =		ids_tensor([self.batch_size]      ,     self.num_labels       )
      A_  :				int	   =		ids_tensor([self.batch_size, self.image_size, self.image_size]      ,     self.num_labels       )

     A_  :				int	   =		self.get_config()

     return config, pixel_values, labels, pixel_labels







    def 					a_  (							self   :					List[Any]       ):



     """simple docstring"""

     return MobileNetVaConfig(
         num_channels=self.num_channels      ,     image_size=self.image_size      ,     depth_multiplier=self.depth_multiplier      ,     min_depth=self.min_depth      ,     tf_padding=self.tf_padding      ,     hidden_act=self.hidden_act      ,     classifier_dropout_prob=self.classifier_dropout_prob      ,     initializer_range=self.initializer_range      ,     )







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



     """simple docstring"""

     A_  :				Dict	   =		MobileNetVaModel(config=_lowerCamelCase       )
     model.to(_lowerCamelCase       )
     model.eval()
     A_  :				List[Any]	   =		model(_lowerCamelCase       )
     self.parent.assertEqual(
         result.last_hidden_state.shape      ,     (
             self.batch_size,
             self.last_hidden_size,
             self.image_size // self.output_stride,
             self.image_size // self.output_stride,
         )      ,     )







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



     """simple docstring"""

     A_  :				Tuple	   =		self.num_labels
     A_  :				Optional[Any]	   =		MobileNetVaForImageClassification(_lowerCamelCase       )
     model.to(_lowerCamelCase       )
     model.eval()
     A_  :				Any	   =		model(_lowerCamelCase      ,     labels=_lowerCamelCase       )
     self.parent.assertEqual(result.logits.shape      ,     (self.batch_size, self.num_labels)       )







    def 					a_  (							self   :					Any       ):



     """simple docstring"""

     A_  :				List[Any]	   =		self.prepare_config_and_inputs()
     A_   , A_   , A_   , A_  :				Optional[int]	   =		config_and_inputs
     A_  :				List[Any]	   =		{'''pixel_values''': pixel_values}
     return config, inputs_dict

@require_torch
class        lowercase      (    lowerCAmelCase__     ,	lowerCAmelCase__     ,	unittest.TestCase):
    __lowerCAmelCase    :    List[str]         =   (MobileNetVaModel, MobileNetVaForImageClassification) if is_torch_available() else ()
    __lowerCAmelCase    :    Dict         =   (
        {"feature-extraction": MobileNetVaModel, "image-classification": MobileNetVaForImageClassification}
        if is_torch_available()
        else {}
    )

    __lowerCAmelCase    :    Tuple         =   False
    __lowerCAmelCase    :    List[Any]         =   False
    __lowerCAmelCase    :    Optional[Any]         =   False
    __lowerCAmelCase    :    Tuple         =   False







    def 					a_  (							self   :					Tuple       ):



     """simple docstring"""

     A_  :				Union[str, Any]	   =		MobileNetVaModelTester(self       )
     A_  :				Optional[int]	   =		MobileNetVaConfigTester(self      ,     config_class=_lowerCamelCase      ,     has_text_modality=_lowerCamelCase       )







    def 					a_  (							self   :					Optional[Any]       ):



     """simple docstring"""

     self.config_tester.run_common_tests()







    @unittest.skip(reason='''MobileNetV1 does not use inputs_embeds'''       )
    def 					a_  (							self   :					Union[str, Any]       ):



     """simple docstring"""

     pass







    @unittest.skip(reason='''MobileNetV1 does not support input and output embeddings'''       )
    def 					a_  (							self   :					List[Any]       ):



     """simple docstring"""

     pass







    @unittest.skip(reason='''MobileNetV1 does not output attentions'''       )
    def 					a_  (							self   :					List[str]       ):



     """simple docstring"""

     pass







    def 					a_  (							self   :					List[Any]       ):



     """simple docstring"""

     A_   , A_  :				Optional[Any]	   =		self.model_tester.prepare_config_and_inputs_for_common()

     for model_class in self.all_model_classes:
      A_  :				Dict	   =		model_class(_lowerCamelCase       )
      A_  :				List[Any]	   =		inspect.signature(model.forward       )
      # signature.parameters is an OrderedDict => so arg_names order is deterministic
      A_  :				Union[str, Any]	   =		[*signature.parameters.keys()]

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







    def 					a_  (							self   :					Any       ):



     """simple docstring"""

     A_  :				Optional[Any]	   =		self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_model(*_lowerCamelCase       )







    def 					a_  (							self   :					Optional[int]       ):



     """simple docstring"""

     def check_hidden_states_output(_lowerCamelCase   :					List[str]      ,     _lowerCamelCase   :					str      ,     _lowerCamelCase   :					Dict       ):
      A_  :				int	   =		model_class(_lowerCamelCase       )
      model.to(_lowerCamelCase       )
      model.eval()

      with torch.no_grad():
       A_  :				Tuple	   =		model(**self._prepare_for_class(_lowerCamelCase      ,     _lowerCamelCase       )       )

      A_  :				str	   =		outputs.hidden_states

      A_  :				int	   =		26
      self.assertEqual(len(_lowerCamelCase       )      ,     _lowerCamelCase       )

     A_   , A_  :				Optional[Any]	   =		self.model_tester.prepare_config_and_inputs_for_common()

     for model_class in self.all_model_classes:
      A_  :				Tuple	   =		True
      check_hidden_states_output(_lowerCamelCase      ,     _lowerCamelCase      ,     _lowerCamelCase       )

      # check that output_hidden_states also work using config
      del inputs_dict["output_hidden_states"]
      A_  :				Any	   =		True

      check_hidden_states_output(_lowerCamelCase      ,     _lowerCamelCase      ,     _lowerCamelCase       )







    def 					a_  (							self   :					str       ):



     """simple docstring"""

     A_  :				Optional[Any]	   =		self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_image_classification(*_lowerCamelCase       )







    @slow
    def 					a_  (							self   :					List[str]       ):



     """simple docstring"""

     for model_name in MOBILENET_V1_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
      A_  :				Any	   =		MobileNetVaModel.from_pretrained(_lowerCamelCase       )
      self.assertIsNotNone(_lowerCamelCase       )

def 		lowercase_      (		):




 """simple docstring"""






 A_  :				int	   =		Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''	)
 return image

@require_torch
@require_vision
class        lowercase      (    unittest.TestCase):







    @cached_property
    def 					a_  (							self   :					Optional[Any]       ):



     """simple docstring"""

     return (
         MobileNetVaImageProcessor.from_pretrained('''google/mobilenet_v1_1.0_224'''       ) if is_vision_available() else None
     )







    @slow
    def 					a_  (							self   :					Optional[Any]       ):



     """simple docstring"""

     A_  :				Optional[Any]	   =		MobileNetVaForImageClassification.from_pretrained('''google/mobilenet_v1_1.0_224'''       ).to(_lowerCamelCase       )

     A_  :				str	   =		self.default_image_processor
     A_  :				Tuple	   =		prepare_img()
     A_  :				str	   =		image_processor(images=_lowerCamelCase      ,     return_tensors='''pt'''       ).to(_lowerCamelCase       )

     # forward pass
     with torch.no_grad():
      A_  :				Any	   =		model(**_lowerCamelCase       )

     # verify the logits
     A_  :				str	   =		torch.Size((1, 10_01)       )
     self.assertEqual(outputs.logits.shape      ,     _lowerCamelCase       )

     A_  :				int	   =		torch.tensor([-4.1739, -1.1233, 3.1205]       ).to(_lowerCamelCase       )

     self.assertTrue(torch.allclose(outputs.logits[0, :3]      ,     _lowerCamelCase      ,     atol=1E-4       )       )











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





