






'''simple docstring'''




import collections
import inspect
import unittest

from transformers import FocalNetConfig
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_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch
		from torch import nn

		from transformers import (
		    FocalNetBackbone,
		    FocalNetForImageClassification,
		    FocalNetForMaskedImageModeling,
		    FocalNetModel,
		)
		from transformers.models.focalnet.modeling_focalnet import FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
		from PIL import Image

		from transformers import AutoImageProcessor







class    A_	:
							"""simple docstring"""




							def __init__(		self			:str       ,							lowerCAmelCase__			:Optional[Any]       ,							lowerCAmelCase__			:List[str]=13       ,							lowerCAmelCase__			:Any=32       ,							lowerCAmelCase__			:Tuple=2       ,							lowerCAmelCase__			:Tuple=3       ,							lowerCAmelCase__			:Dict=16       ,							lowerCAmelCase__			:Optional[int]=[32, 64, 128]       ,							lowerCAmelCase__			:int=[1, 2, 1]       ,							lowerCAmelCase__			:Union[str, Any]=[2, 2, 4]       ,							lowerCAmelCase__			:Optional[int]=2       ,							lowerCAmelCase__			:Tuple=2.0       ,							lowerCAmelCase__			:Optional[Any]=True       ,							lowerCAmelCase__			:List[str]=0.0       ,							lowerCAmelCase__			:List[Any]=0.0       ,							lowerCAmelCase__			:int=0.1       ,							lowerCAmelCase__			:Any="gelu"       ,							lowerCAmelCase__			:int=False       ,							lowerCAmelCase__			:str=True       ,							lowerCAmelCase__			:Optional[int]=0.0_2       ,							lowerCAmelCase__			:str=1E-5       ,							lowerCAmelCase__			:Optional[Any]=True       ,							lowerCAmelCase__			:Dict=None       ,							lowerCAmelCase__			:Any=True       ,							lowerCAmelCase__			:Union[str, Any]=10       ,							lowerCAmelCase__			:Dict=8       ,							lowerCAmelCase__			:Optional[int]=["stage1", "stage2"]       ,							lowerCAmelCase__			:Union[str, Any]=[1, 2]       ,							)				->  Optional[Any]:


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       parent
										snake_case_				:					Dict   =       batch_size
										snake_case_				:					str   =       image_size
										snake_case_				:					Dict   =       patch_size
										snake_case_				:					Union[str, Any]   =       num_channels
										snake_case_				:					Optional[int]   =       embed_dim
										snake_case_				:					List[Any]   =       hidden_sizes
										snake_case_				:					Optional[int]   =       depths
										snake_case_				:					Tuple   =       num_heads
										snake_case_				:					str   =       window_size
										snake_case_				:					List[Any]   =       mlp_ratio
										snake_case_				:					List[Any]   =       qkv_bias
										snake_case_				:					List[str]   =       hidden_dropout_prob
										snake_case_				:					Optional[Any]   =       attention_probs_dropout_prob
										snake_case_				:					Tuple   =       drop_path_rate
										snake_case_				:					Union[str, Any]   =       hidden_act
										snake_case_				:					Optional[int]   =       use_absolute_embeddings
										snake_case_				:					str   =       patch_norm
										snake_case_				:					Optional[int]   =       layer_norm_eps
										snake_case_				:					Union[str, Any]   =       initializer_range
										snake_case_				:					str   =       is_training
										snake_case_				:					Any   =       scope
										snake_case_				:					Optional[int]   =       use_labels
										snake_case_				:					Dict   =       type_sequence_label_size
										snake_case_				:					Optional[Any]   =       encoder_stride
										snake_case_				:					str   =       out_features
										snake_case_				:					List[str]   =       out_indices

							def 							_A	(		self			:int				)				->  Union[str, Any]:


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]				)

										snake_case_				:					List[str]   =       None
										if self.use_labels:
													snake_case_				:					int   =       ids_tensor([self.batch_size]       ,							self.type_sequence_label_size				)

										snake_case_				:					Dict   =       self.get_config()

										return config, pixel_values, labels

							def 							_A	(		self			:str				)				->  Optional[int]:


										'''simple docstring'''




										return FocalNetConfig(
										    image_size=self.image_size       ,							patch_size=self.patch_size       ,							num_channels=self.num_channels       ,							embed_dim=self.embed_dim       ,							hidden_sizes=self.hidden_sizes       ,							depths=self.depths       ,							num_heads=self.num_heads       ,							window_size=self.window_size       ,							mlp_ratio=self.mlp_ratio       ,							qkv_bias=self.qkv_bias       ,							hidden_dropout_prob=self.hidden_dropout_prob       ,							attention_probs_dropout_prob=self.attention_probs_dropout_prob       ,							drop_path_rate=self.drop_path_rate       ,							hidden_act=self.hidden_act       ,							use_absolute_embeddings=self.use_absolute_embeddings       ,							path_norm=self.patch_norm       ,							layer_norm_eps=self.layer_norm_eps       ,							initializer_range=self.initializer_range       ,							encoder_stride=self.encoder_stride       ,							out_features=self.out_features       ,							out_indices=self.out_indices       ,							)

							def 							_A	(		self			:List[str]       ,							lowerCAmelCase__			:Dict       ,							lowerCAmelCase__			:Optional[int]       ,							lowerCAmelCase__			:Optional[Any]				)				->  Optional[Any]:


										'''simple docstring'''




										snake_case_				:					int   =       FocalNetModel(config=lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()
										snake_case_				:					int   =       model(lowerCAmelCase__				)

										snake_case_				:					Dict   =       ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths				) - 1))
										snake_case_				:					Optional[Any]   =       int(config.embed_dim * 2 ** (len(config.depths				) - 1)				)

										self.parent.assertEqual(result.last_hidden_state.shape       ,							(self.batch_size, expected_seq_len, expected_dim)				)

							def 							_A	(		self			:str       ,							lowerCAmelCase__			:List[Any]       ,							lowerCAmelCase__			:int       ,							lowerCAmelCase__			:Any				)				->  int:


										'''simple docstring'''




										snake_case_				:					int   =       FocalNetBackbone(config=lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()
										snake_case_				:					Optional[int]   =       model(lowerCAmelCase__				)

										# verify feature maps
										self.parent.assertEqual(len(result.feature_maps				)       ,							len(config.out_features				)				)
										self.parent.assertListEqual(list(result.feature_maps[0].shape				)       ,							[self.batch_size, self.image_size, 8, 8]				)

										# verify channels
										self.parent.assertEqual(len(model.channels				)       ,							len(config.out_features				)				)
										self.parent.assertListEqual(model.channels       ,							config.hidden_sizes[:-1]				)

										# verify backbone works with out_features=None
										snake_case_				:					str   =       None
										snake_case_				:					Optional[int]   =       FocalNetBackbone(config=lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()
										snake_case_				:					Any   =       model(lowerCAmelCase__				)

										# verify feature maps
										self.parent.assertEqual(len(result.feature_maps				)       ,							1				)
										self.parent.assertListEqual(list(result.feature_maps[0].shape				)       ,							[self.batch_size, self.image_size * 2, 4, 4]				)

										# verify channels
										self.parent.assertEqual(len(model.channels				)       ,							1				)
										self.parent.assertListEqual(model.channels       ,							[config.hidden_sizes[-1]]				)

							def 							_A	(		self			:List[str]       ,							lowerCAmelCase__			:int       ,							lowerCAmelCase__			:List[str]       ,							lowerCAmelCase__			:int				)				->  Tuple:


										'''simple docstring'''




										snake_case_				:					Any   =       FocalNetForMaskedImageModeling(config=lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()
										snake_case_				:					str   =       model(lowerCAmelCase__				)
										self.parent.assertEqual(
										    result.reconstruction.shape       ,							(self.batch_size, self.num_channels, self.image_size, self.image_size)				)

										# test greyscale images
										snake_case_				:					Optional[Any]   =       1
										snake_case_				:					int   =       FocalNetForMaskedImageModeling(lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()

										snake_case_				:					Dict   =       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]				)
										snake_case_				:					Tuple   =       model(lowerCAmelCase__				)
										self.parent.assertEqual(result.reconstruction.shape       ,							(self.batch_size, 1, self.image_size, self.image_size)				)

							def 							_A	(		self			:Optional[int]       ,							lowerCAmelCase__			:Dict       ,							lowerCAmelCase__			:Tuple       ,							lowerCAmelCase__			:List[Any]				)				->  List[str]:


										'''simple docstring'''




										snake_case_				:					Dict   =       self.type_sequence_label_size
										snake_case_				:					Any   =       FocalNetForImageClassification(lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()
										snake_case_				:					Optional[int]   =       model(lowerCAmelCase__       ,							labels=lowerCAmelCase__				)
										self.parent.assertEqual(result.logits.shape       ,							(self.batch_size, self.type_sequence_label_size)				)

										# test greyscale images
										snake_case_				:					Tuple   =       1
										snake_case_				:					List[str]   =       FocalNetForImageClassification(lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()

										snake_case_				:					List[str]   =       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]				)
										snake_case_				:					int   =       model(lowerCAmelCase__				)
										self.parent.assertEqual(result.logits.shape       ,							(self.batch_size, self.type_sequence_label_size)				)






							def 							_A	(		self			:List[Any]				)				->  int:


										'''simple docstring'''




										snake_case_				:					Union[str, Any]   =       self.prepare_config_and_inputs()

										snake_case_,	snake_case_,	snake_case_				:					List[str]   =       config_and_inputs
										snake_case_				:					Union[str, Any]   =       {"pixel_values": pixel_values}
										return config, inputs_dict







@require_torch
class    A_	(a_						,					a_						,					unittest.TestCase							):
							"""simple docstring"""




							a__   		=	(
							    (
							        FocalNetModel,
							        FocalNetForImageClassification,
							        FocalNetForMaskedImageModeling,
							        FocalNetBackbone,
							    )
							    if is_torch_available()
							    else ()
							)
							a__   		=	(
							    {'''feature-extraction''': FocalNetModel, '''image-classification''': FocalNetForImageClassification}
							    if is_torch_available()
							    else {}
							)
							a__   		=	False

							a__   		=	False
							a__   		=	False
							a__   		=	False
							a__   		=	False

							def 							_A	(		self			:Any				)				->  Any:


										'''simple docstring'''




										snake_case_				:					Union[str, Any]   =       FocalNetModelTester(self				)
										snake_case_				:					Dict   =       ConfigTester(self       ,							config_class=lowerCAmelCase__       ,							embed_dim=37       ,							has_text_modality=lowerCAmelCase__				)

							def 							_A	(		self			:Dict				)				->  Dict:


										'''simple docstring'''




										self.create_and_test_config_common_properties()
										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 							_A	(		self			:List[Any]				)				->  Any:


										'''simple docstring'''




										return

							def 							_A	(		self			:Optional[int]				)				->  List[Any]:


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_model(*lowerCAmelCase__				)

							def 							_A	(		self			:List[Any]				)				->  Tuple:


										'''simple docstring'''




										snake_case_				:					List[Any]   =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_backbone(*lowerCAmelCase__				)

							def 							_A	(		self			:str				)				->  Tuple:


										'''simple docstring'''




										snake_case_				:					int   =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_masked_image_modeling(*lowerCAmelCase__				)

							def 							_A	(		self			:Any				)				->  List[Any]:


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_image_classification(*lowerCAmelCase__				)

							@unittest.skip(reason="FocalNet does not use inputs_embeds"				)
							def 							_A	(		self			:Tuple				)				->  Any:


										'''simple docstring'''




										pass

							@unittest.skip(reason="FocalNet does not use feedforward chunking"				)
							def 							_A	(		self			:Any				)				->  List[str]:


										'''simple docstring'''




										pass

							def 							_A	(		self			:Tuple				)				->  List[Any]:


										'''simple docstring'''




										snake_case_,	snake_case_				:					List[Any]   =       self.model_tester.prepare_config_and_inputs_for_common()

										for model_class in self.all_model_classes[:-1]:
													snake_case_				:					str   =       model_class(lowerCAmelCase__				)
													self.assertIsInstance(model.get_input_embeddings()       ,							(nn.Module)				)
													snake_case_				:					Any   =       model.get_output_embeddings()
													self.assertTrue(x is None or isinstance(lowerCAmelCase__       ,							nn.Linear				)				)

							def 							_A	(		self			:List[Any]				)				->  Optional[Any]:


										'''simple docstring'''




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

										for model_class in self.all_model_classes[:-1]:
													snake_case_				:					int   =       model_class(lowerCAmelCase__				)
													snake_case_				:					Dict   =       inspect.signature(model.forward				)
													# signature.parameters is an OrderedDict => so arg_names order is deterministic
													snake_case_				:					Optional[int]   =       [*signature.parameters.keys()]

													snake_case_				:					List[str]   =       ["pixel_values"]
													self.assertListEqual(arg_names[:1]       ,							lowerCAmelCase__				)

							def 							_A	(		self			:List[Any]       ,							lowerCAmelCase__			:Dict       ,							lowerCAmelCase__			:Optional[Any]       ,							lowerCAmelCase__			:str       ,							lowerCAmelCase__			:str				)				->  List[Any]:


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       model_class(lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()

										with torch.no_grad():
													snake_case_				:					int   =       model(**self._prepare_for_class(lowerCAmelCase__       ,							lowerCAmelCase__				)				)

										snake_case_				:					int   =       outputs.hidden_states

										snake_case_				:					Dict   =       getattr(
										    self.model_tester       ,							"expected_num_hidden_layers"       ,							len(self.model_tester.depths				) + 1				)
										self.assertEqual(len(lowerCAmelCase__				)       ,							lowerCAmelCase__				)

										# FocalNet has a different seq_length
										snake_case_				:					Tuple   =       (
										    config.patch_size
										    if isinstance(config.patch_size       ,							collections.abc.Iterable				)
										    else (config.patch_size, config.patch_size)
										)

										snake_case_				:					List[Any]   =       (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

										self.assertListEqual(
										    list(hidden_states[0].shape[-2:]				)       ,							[num_patches, self.model_tester.embed_dim]       ,							)

										snake_case_				:					List[str]   =       outputs.reshaped_hidden_states
										self.assertEqual(len(lowerCAmelCase__				)       ,							lowerCAmelCase__				)

										snake_case_,	snake_case_,	snake_case_,	snake_case_				:					Union[str, Any]   =       reshaped_hidden_states[0].shape
										snake_case_				:					Union[str, Any]   =       (
										    reshaped_hidden_states[0].view(lowerCAmelCase__       ,							lowerCAmelCase__       ,							height * width				).permute(0       ,							2       ,							1				)
										)
										self.assertListEqual(
										    list(reshaped_hidden_states.shape[-2:]				)       ,							[num_patches, self.model_tester.embed_dim]       ,							)

							def 							_A	(		self			:Optional[int]				)				->  Dict:


										'''simple docstring'''




										snake_case_,	snake_case_				:					Tuple   =       self.model_tester.prepare_config_and_inputs_for_common()

										snake_case_				:					Optional[Any]   =       (
										    self.model_tester.image_size
										    if isinstance(self.model_tester.image_size       ,							collections.abc.Iterable				)
										    else (self.model_tester.image_size, self.model_tester.image_size)
										)

										for model_class in self.all_model_classes[:-1]:
													snake_case_				:					Tuple   =       True
													self.check_hidden_states_output(lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__				)

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

													self.check_hidden_states_output(lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__				)

							def 							_A	(		self			:Optional[Any]				)				->  Dict:


										'''simple docstring'''




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

										snake_case_				:					Tuple   =       (
										    self.model_tester.image_size
										    if isinstance(self.model_tester.image_size       ,							collections.abc.Iterable				)
										    else (self.model_tester.image_size, self.model_tester.image_size)
										)
										snake_case_				:					Optional[Any]   =       (
										    config.patch_size
										    if isinstance(config.patch_size       ,							collections.abc.Iterable				)
										    else (config.patch_size, config.patch_size)
										)

										snake_case_				:					Union[str, Any]   =       image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
										snake_case_				:					List[Any]   =       image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

										for model_class in self.all_model_classes[:-1]:
													snake_case_				:					Union[str, Any]   =       True
													self.check_hidden_states_output(lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__       ,							(padded_height, padded_width)				)

													# check that output_hidden_states also work using config
													del inputs_dict["output_hidden_states"]
													snake_case_				:					Union[str, Any]   =       True
													self.check_hidden_states_output(lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__       ,							(padded_height, padded_width)				)

							@slow
							def 							_A	(		self			:Optional[Any]				)				->  str:


										'''simple docstring'''




										for model_name in FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
													snake_case_				:					Any   =       FocalNetModel.from_pretrained(lowerCAmelCase__				)
													self.assertIsNotNone(lowerCAmelCase__				)






							def 							_A	(		self			:Union[str, Any]				)				->  Tuple:


										'''simple docstring'''




										snake_case_,	snake_case_				:					Tuple   =       self.model_tester.prepare_config_and_inputs_for_common()

										snake_case_				:					Tuple   =       _config_zero_init(lowerCAmelCase__				)
										for model_class in self.all_model_classes:
													snake_case_				:					str   =       model_class(config=lowerCAmelCase__				)
													for name, param in model.named_parameters():
																if "embeddings" not in name and param.requires_grad:
																			self.assertIn(
																			    ((param.data.mean() * 1E9).round() / 1E9).item()       ,							[0.0, 1.0]       ,							msg=F'''Parameter {name} of model {model_class} seems not properly initialized'''       ,							)







@require_vision
@require_torch
class    A_	(unittest.TestCase							):
							"""simple docstring"""




							@cached_property
							def 							_A	(		self			:Tuple				)				->  int:


										'''simple docstring'''




										return AutoImageProcessor.from_pretrained("microsoft/focalnet-tiny"				) if is_vision_available() else None






							@slow
							def 							_A	(		self			:str				)				->  Union[str, Any]:


										'''simple docstring'''




										snake_case_				:					List[str]   =       FocalNetForImageClassification.from_pretrained("microsoft/focalnet-tiny"				).to(lowerCAmelCase__				)
										snake_case_				:					str   =       self.default_image_processor

										snake_case_				:					Dict   =       Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"				)
										snake_case_				:					Any   =       image_processor(images=lowerCAmelCase__       ,							return_tensors="pt"				).to(lowerCAmelCase__				)

										# forward pass
										with torch.no_grad():
													snake_case_				:					str   =       model(**lowerCAmelCase__				)

										# verify the logits
										snake_case_				:					List[str]   =       torch.Size((1, 1_000)				)
										self.assertEqual(outputs.logits.shape       ,							lowerCAmelCase__				)
										snake_case_				:					Tuple   =       torch.tensor([0.2_1_6_6, -0.4_3_6_8, 0.2_1_9_1]				).to(lowerCAmelCase__				)
										self.assertTrue(torch.allclose(outputs.logits[0, :3]       ,							lowerCAmelCase__       ,							atol=1E-4				)				)
										self.assertTrue(outputs.logits.argmax(dim=-1				).item()       ,							281				)







@require_torch
class    A_	(a_						,					unittest.TestCase							):
							"""simple docstring"""




							a__   		=	(FocalNetBackbone,) if is_torch_available() else ()
							a__   		=	FocalNetConfig

							a__   		=	False

							def 							_A	(		self			:Any				)				->  List[Any]:


										'''simple docstring'''




										snake_case_				:					Any   =       FocalNetModelTester(self				)












'''simple docstring'''




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







class    A_	:
							"""simple docstring"""




							def __init__(		self			:Dict				)				->  List[str]:


										'''simple docstring'''




										snake_case_				:					int   =       {}

							def 							_A	(		self			:Any       ,							lowerCAmelCase__			:Optional[Any]       ,							lowerCAmelCase__			:Tuple       ,							lowerCAmelCase__			:Optional[Any]=1				)				->  Any:


										'''simple docstring'''




										if self.graph.get(lowerCAmelCase__				):
													if self.graph[u].count([w, v]				) == 0:
																self.graph[u].append([w, v]				)
										else:
													snake_case_				:					Optional[int]   =       [[w, v]]
										if not self.graph.get(lowerCAmelCase__				):
													snake_case_				:					Dict   =       []

							def 							_A	(		self			:List[Any]				)				->  Optional[int]:


										'''simple docstring'''




										return list(self.graph				)

							def 							_A	(		self			:str       ,							lowerCAmelCase__			:Any       ,							lowerCAmelCase__			:int				)				->  List[Any]:


										'''simple docstring'''




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

							def 							_A	(		self			:List[str]       ,							lowerCAmelCase__			:Optional[Any]=-2       ,							lowerCAmelCase__			:str=-1				)				->  str:


										'''simple docstring'''




										if s == d:
													return []
										snake_case_				:					str   =       []
										snake_case_				:					Optional[int]   =       []
										if s == -2:
													snake_case_				:					List[Any]   =       list(self.graph				)[0]
										stack.append(lowerCAmelCase__				)
										visited.append(lowerCAmelCase__				)
										snake_case_				:					Dict   =       s

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

            # check if all the children are visited
													if s == ss:
																stack.pop()
																if len(lowerCAmelCase__				) != 0:
																			snake_case_				:					Union[str, Any]   =       stack[len(lowerCAmelCase__				) - 1]
													else:
																snake_case_				:					Optional[Any]   =       ss

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

							def 							_A	(		self			:Tuple       ,							lowerCAmelCase__			:int=-1				)				->  int:


										'''simple docstring'''




										if c == -1:
													snake_case_				:					Any   =       floor(random() * 10_000				) + 10
										for i in range(lowerCAmelCase__				):
													# every vertex has max 100 edges
													for _ in range(floor(random() * 102				) + 1				):
																snake_case_				:					Optional[Any]   =       floor(random() * c				) + 1
																if n != i:
																			self.add_pair(lowerCAmelCase__       ,							lowerCAmelCase__       ,							1				)

							def 							_A	(		self			:Tuple       ,							lowerCAmelCase__			:Dict=-2				)				->  Dict:


										'''simple docstring'''




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


										'''simple docstring'''




										snake_case_				:					Tuple   =       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__			:int				)				->  Optional[Any]:


										'''simple docstring'''




										return len(self.graph[u]				)

							def 							_A	(		self			:Tuple       ,							lowerCAmelCase__			:List[str]=-2				)				->  Optional[Any]:


										'''simple docstring'''




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

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

            # check if all the children are visited
													if s == ss:
																sorted_nodes.append(stack.pop()				)
																if len(lowerCAmelCase__				) != 0:
																			snake_case_				:					int   =       stack[len(lowerCAmelCase__				) - 1]
													else:
																snake_case_				:					Union[str, Any]   =       ss

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

							def 							_A	(		self			:Dict				)				->  Any:


										'''simple docstring'''




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

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

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

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

							def 							_A	(		self			:Tuple				)				->  List[str]:


										'''simple docstring'''




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

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

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

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

							def 							_A	(		self			:Optional[int]       ,							lowerCAmelCase__			:Optional[int]=-2       ,							lowerCAmelCase__			:Tuple=-1				)				->  str:


										'''simple docstring'''




										snake_case_				:					Optional[int]   =       time()
										self.dfs(lowerCAmelCase__       ,							lowerCAmelCase__				)
										snake_case_				:					Optional[Any]   =       time()
										return end - begin






							def 							_A	(		self			:Any       ,							lowerCAmelCase__			:Tuple=-2				)				->  Optional[Any]:


										'''simple docstring'''




										snake_case_				:					Any   =       time()
										self.bfs(lowerCAmelCase__				)
										snake_case_				:					Any   =       time()
										return end - begin







class    A_	:
							"""simple docstring"""




							def __init__(		self			:Tuple				)				->  List[str]:


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       {}

							def 							_A	(		self			:str       ,							lowerCAmelCase__			:Dict       ,							lowerCAmelCase__			:List[Any]       ,							lowerCAmelCase__			:Union[str, Any]=1				)				->  str:


										'''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
													snake_case_				:					str   =       [[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
													snake_case_				:					List[str]   =       [[w, u]]

							def 							_A	(		self			:Dict       ,							lowerCAmelCase__			:Tuple       ,							lowerCAmelCase__			:Optional[Any]				)				->  Optional[Any]:


										'''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			:Optional[Any]       ,							lowerCAmelCase__			:Optional[Any]=-2       ,							lowerCAmelCase__			:Optional[int]=-1				)				->  int:


										'''simple docstring'''




										if s == d:
													return []
										snake_case_				:					Any   =       []
										snake_case_				:					Dict   =       []
										if s == -2:
													snake_case_				:					Optional[int]   =       list(self.graph				)[0]
										stack.append(lowerCAmelCase__				)
										visited.append(lowerCAmelCase__				)
										snake_case_				:					Tuple   =       s

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

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

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

							def 							_A	(		self			:Optional[int]       ,							lowerCAmelCase__			:str=-1				)				->  List[Any]:


										'''simple docstring'''




										if c == -1:
													snake_case_				:					Optional[int]   =       floor(random() * 10_000				) + 10
										for i in range(lowerCAmelCase__				):
													# every vertex has max 100 edges
													for _ in range(floor(random() * 102				) + 1				):
																snake_case_				:					str   =       floor(random() * c				) + 1
																if n != i:
																			self.add_pair(lowerCAmelCase__       ,							lowerCAmelCase__       ,							1				)

							def 							_A	(		self			:Any       ,							lowerCAmelCase__			:Optional[Any]=-2				)				->  List[Any]:


										'''simple docstring'''




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


										'''simple docstring'''




										return len(self.graph[u]				)

							def 							_A	(		self			:Union[str, Any]				)				->  Dict:


										'''simple docstring'''




										snake_case_				:					Any   =       []
										snake_case_				:					Optional[Any]   =       []
										snake_case_				:					Optional[Any]   =       list(self.graph				)[0]
										stack.append(lowerCAmelCase__				)
										visited.append(lowerCAmelCase__				)
										snake_case_				:					Tuple   =       -2
										snake_case_				:					Optional[int]   =       []
										snake_case_				:					Tuple   =       s
										snake_case_				:					Optional[Any]   =       False
										snake_case_				:					Optional[int]   =       set()

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

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

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

							def 							_A	(		self			:Optional[Any]				)				->  Tuple:


										'''simple docstring'''




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

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

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

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

							def 							_A	(		self			:Any				)				->  Tuple:


										'''simple docstring'''




										return list(self.graph				)

							def 							_A	(		self			:Optional[Any]       ,							lowerCAmelCase__			:Tuple=-2       ,							lowerCAmelCase__			:Optional[int]=-1				)				->  str:


										'''simple docstring'''




										snake_case_				:					List[str]   =       time()
										self.dfs(lowerCAmelCase__       ,							lowerCAmelCase__				)
										snake_case_				:					List[Any]   =       time()
										return end - begin






							def 							_A	(		self			:Union[str, Any]       ,							lowerCAmelCase__			:List[Any]=-2				)				->  int:


										'''simple docstring'''




										snake_case_				:					List[str]   =       time()
										self.bfs(lowerCAmelCase__				)
										snake_case_				:					Tuple   =       time()
										return end - begin




