






'''simple docstring'''




import inspect
import unittest

from transformers import YolosConfig
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
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch
		from torch import nn

		from transformers import YolosForObjectDetection, YolosModel
		from transformers.models.yolos.modeling_yolos import YOLOS_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
		from PIL import Image

		from transformers import AutoImageProcessor







class    A_	:
							"""simple docstring"""




							def __init__(		self			:List[Any]       ,							lowerCAmelCase__			:str       ,							lowerCAmelCase__			:Union[str, Any]=13       ,							lowerCAmelCase__			:int=[30, 30]       ,							lowerCAmelCase__			:int=2       ,							lowerCAmelCase__			:Tuple=3       ,							lowerCAmelCase__			:List[str]=True       ,							lowerCAmelCase__			:Optional[Any]=True       ,							lowerCAmelCase__			:str=32       ,							lowerCAmelCase__			:Tuple=5       ,							lowerCAmelCase__			:Any=4       ,							lowerCAmelCase__			:str=37       ,							lowerCAmelCase__			:List[str]="gelu"       ,							lowerCAmelCase__			:Any=0.1       ,							lowerCAmelCase__			:int=0.1       ,							lowerCAmelCase__			:Union[str, Any]=10       ,							lowerCAmelCase__			:int=0.0_2       ,							lowerCAmelCase__			:str=3       ,							lowerCAmelCase__			:Any=None       ,							lowerCAmelCase__			:List[Any]=8       ,							lowerCAmelCase__			:Optional[Any]=10       ,							)				->  int:


										'''simple docstring'''




										snake_case_				:					str   =       parent
										snake_case_				:					Optional[int]   =       batch_size
										snake_case_				:					Union[str, Any]   =       image_size
										snake_case_				:					str   =       patch_size
										snake_case_				:					List[str]   =       num_channels
										snake_case_				:					str   =       is_training
										snake_case_				:					int   =       use_labels
										snake_case_				:					Optional[Any]   =       hidden_size
										snake_case_				:					int   =       num_hidden_layers
										snake_case_				:					int   =       num_attention_heads
										snake_case_				:					List[Any]   =       intermediate_size
										snake_case_				:					Tuple   =       hidden_act
										snake_case_				:					List[Any]   =       hidden_dropout_prob
										snake_case_				:					int   =       attention_probs_dropout_prob
										snake_case_				:					Union[str, Any]   =       type_sequence_label_size
										snake_case_				:					Dict   =       initializer_range
										snake_case_				:					List[str]   =       num_labels
										snake_case_				:					Optional[Any]   =       scope
										snake_case_				:					Dict   =       n_targets
										snake_case_				:					int   =       num_detection_tokens
										# we set the expected sequence length (which is used in several tests)
										# expected sequence length = num_patches + 1 (we add 1 for the [CLS] token) + num_detection_tokens
										snake_case_				:					Union[str, Any]   =       (image_size[1] // patch_size) * (image_size[0] // patch_size)
										snake_case_				:					List[str]   =       num_patches + 1 + self.num_detection_tokens

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


										'''simple docstring'''




										snake_case_				:					Union[str, Any]   =       floats_tensor([self.batch_size, self.num_channels, self.image_size[0], self.image_size[1]]				)

										snake_case_				:					Dict   =       None
										if self.use_labels:
													# labels is a list of Dict (each Dict being the labels for a given example in the batch)
													snake_case_				:					Tuple   =       []
													for i in range(self.batch_size				):
																snake_case_				:					Tuple   =       {}
																snake_case_				:					Optional[int]   =       torch.randint(
																    high=self.num_labels       ,							size=(self.n_targets,)       ,							device=lowerCAmelCase__				)
																snake_case_				:					int   =       torch.rand(self.n_targets       ,							4       ,							device=lowerCAmelCase__				)
																labels.append(lowerCAmelCase__				)

										snake_case_				:					Dict   =       self.get_config()

										return config, pixel_values, labels

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


										'''simple docstring'''




										return YolosConfig(
										    image_size=self.image_size       ,							patch_size=self.patch_size       ,							num_channels=self.num_channels       ,							hidden_size=self.hidden_size       ,							num_hidden_layers=self.num_hidden_layers       ,							num_attention_heads=self.num_attention_heads       ,							intermediate_size=self.intermediate_size       ,							hidden_act=self.hidden_act       ,							hidden_dropout_prob=self.hidden_dropout_prob       ,							attention_probs_dropout_prob=self.attention_probs_dropout_prob       ,							is_decoder=lowerCAmelCase__       ,							initializer_range=self.initializer_range       ,							num_detection_tokens=self.num_detection_tokens       ,							num_labels=self.num_labels       ,							)

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


										'''simple docstring'''




										snake_case_				:					Any   =       YolosModel(config=lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()
										snake_case_				:					Tuple   =       model(lowerCAmelCase__				)
										self.parent.assertEqual(
										    result.last_hidden_state.shape       ,							(self.batch_size, self.expected_seq_len, self.hidden_size)				)

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


										'''simple docstring'''




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

										snake_case_				:					Dict   =       model(pixel_values=lowerCAmelCase__				)
										snake_case_				:					str   =       model(lowerCAmelCase__				)

										self.parent.assertEqual(result.logits.shape       ,							(self.batch_size, self.num_detection_tokens, self.num_labels + 1)				)
										self.parent.assertEqual(result.pred_boxes.shape       ,							(self.batch_size, self.num_detection_tokens, 4)				)

										snake_case_				:					Optional[int]   =       model(pixel_values=lowerCAmelCase__       ,							labels=lowerCAmelCase__				)

										self.parent.assertEqual(result.loss.shape       ,							()				)
										self.parent.assertEqual(result.logits.shape       ,							(self.batch_size, self.num_detection_tokens, self.num_labels + 1)				)
										self.parent.assertEqual(result.pred_boxes.shape       ,							(self.batch_size, self.num_detection_tokens, 4)				)






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


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       self.prepare_config_and_inputs()
										snake_case_,	snake_case_,	snake_case_				:					int   =       config_and_inputs
										snake_case_				:					str   =       {"pixel_values": pixel_values}
										return config, inputs_dict







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




							a__   		=	(YolosModel, YolosForObjectDetection) if is_torch_available() else ()
							a__   		=	(
							    {'''feature-extraction''': YolosModel, '''object-detection''': YolosForObjectDetection} if is_torch_available() else {}
							)

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

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


										'''simple docstring'''




										snake_case_				:					List[str]   =       super()._prepare_for_class(lowerCAmelCase__       ,							lowerCAmelCase__       ,							return_labels=lowerCAmelCase__				)

										if return_labels:
													if model_class.__name__ == "YolosForObjectDetection":
																snake_case_				:					Optional[Any]   =       []
																for i in range(self.model_tester.batch_size				):
																			snake_case_				:					Optional[Any]   =       {}
																			snake_case_				:					str   =       torch.ones(
																			    size=(self.model_tester.n_targets,)       ,							device=lowerCAmelCase__       ,							dtype=torch.long				)
																			snake_case_				:					int   =       torch.ones(
																			    self.model_tester.n_targets       ,							4       ,							device=lowerCAmelCase__       ,							dtype=torch.float				)
																			labels.append(lowerCAmelCase__				)
																snake_case_				:					Any   =       labels

										return inputs_dict

							def 							_A	(		self			:Tuple				)				->  Tuple:


										'''simple docstring'''




										snake_case_				:					Dict   =       YolosModelTester(self				)
										snake_case_				:					str   =       ConfigTester(self       ,							config_class=lowerCAmelCase__       ,							has_text_modality=lowerCAmelCase__       ,							hidden_size=37				)

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


										'''simple docstring'''




										self.config_tester.run_common_tests()

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


										'''simple docstring'''




										pass

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


										'''simple docstring'''




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

										for model_class in self.all_model_classes:
													snake_case_				:					Any   =       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			:int				)				->  Optional[Any]:


										'''simple docstring'''




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

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

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

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


										'''simple docstring'''




										snake_case_				:					Union[str, Any]   =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_model(*lowerCAmelCase__				)

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


										'''simple docstring'''




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

										# in YOLOS, the seq_len is different
										snake_case_				:					Dict   =       self.model_tester.expected_seq_len
										for model_class in self.all_model_classes:
													snake_case_				:					Dict   =       True
													snake_case_				:					Tuple   =       False
													snake_case_				:					str   =       True
													snake_case_				:					List[Any]   =       model_class(lowerCAmelCase__				)
													model.to(lowerCAmelCase__				)
													model.eval()
													with torch.no_grad():
																snake_case_				:					Union[str, Any]   =       model(**self._prepare_for_class(lowerCAmelCase__       ,							lowerCAmelCase__				)				)
													snake_case_				:					str   =       outputs.attentions
													self.assertEqual(len(lowerCAmelCase__				)       ,							self.model_tester.num_hidden_layers				)

													# check that output_attentions also work using config
													del inputs_dict["output_attentions"]
													snake_case_				:					Optional[int]   =       True
													snake_case_				:					Union[str, Any]   =       model_class(lowerCAmelCase__				)
													model.to(lowerCAmelCase__				)
													model.eval()
													with torch.no_grad():
																snake_case_				:					Optional[Any]   =       model(**self._prepare_for_class(lowerCAmelCase__       ,							lowerCAmelCase__				)				)
													snake_case_				:					int   =       outputs.attentions
													self.assertEqual(len(lowerCAmelCase__				)       ,							self.model_tester.num_hidden_layers				)

													self.assertListEqual(
													    list(attentions[0].shape[-3:]				)       ,							[self.model_tester.num_attention_heads, seq_len, seq_len]       ,							)
													snake_case_				:					Any   =       len(lowerCAmelCase__				)

													# Check attention is always last and order is fine
													snake_case_				:					List[Any]   =       True
													snake_case_				:					Optional[Any]   =       True
													snake_case_				:					Any   =       model_class(lowerCAmelCase__				)
													model.to(lowerCAmelCase__				)
													model.eval()
													with torch.no_grad():
																snake_case_				:					List[str]   =       model(**self._prepare_for_class(lowerCAmelCase__       ,							lowerCAmelCase__				)				)

													snake_case_				:					Optional[Any]   =       1
													self.assertEqual(out_len + added_hidden_states       ,							len(lowerCAmelCase__				)				)

													snake_case_				:					Dict   =       outputs.attentions

													self.assertEqual(len(lowerCAmelCase__				)       ,							self.model_tester.num_hidden_layers				)
													self.assertListEqual(
													    list(self_attentions[0].shape[-3:]				)       ,							[self.model_tester.num_attention_heads, seq_len, seq_len]       ,							)

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


										'''simple docstring'''




										def check_hidden_states_output(lowerCAmelCase__			:str       ,							lowerCAmelCase__			:List[str]       ,							lowerCAmelCase__			:List[str]				):
													snake_case_				:					int   =       model_class(lowerCAmelCase__				)
													model.to(lowerCAmelCase__				)
													model.eval()

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

													snake_case_				:					Union[str, Any]   =       outputs.hidden_states

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

													# YOLOS has a different seq_length
													snake_case_				:					int   =       self.model_tester.expected_seq_len

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

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

										for model_class in self.all_model_classes:
													snake_case_				:					List[Any]   =       True
													check_hidden_states_output(lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__				)

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

													check_hidden_states_output(lowerCAmelCase__       ,							lowerCAmelCase__       ,							lowerCAmelCase__				)

							def 							_A	(		self			:str				)				->  Any:


										'''simple docstring'''




										snake_case_				:					Tuple   =       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_object_detection(*lowerCAmelCase__				)






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


										'''simple docstring'''




										for model_name in YOLOS_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
													snake_case_				:					List[Any]   =       YolosModel.from_pretrained(lowerCAmelCase__				)
													self.assertIsNotNone(lowerCAmelCase__				)

def 	__UpperCAmelCase       ( )->    int:



			"""simple docstring"""



			snake_case_				:					Union[str, Any]   =       Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"						)
			return image







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




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


										'''simple docstring'''




										return AutoImageProcessor.from_pretrained("hustvl/yolos-small"				) if is_vision_available() else None






							@slow
							def 							_A	(		self			:Tuple				)				->  Tuple:


										'''simple docstring'''




										snake_case_				:					str   =       YolosForObjectDetection.from_pretrained("hustvl/yolos-small"				).to(lowerCAmelCase__				)

										snake_case_				:					Dict   =       self.default_image_processor
										snake_case_				:					List[str]   =       prepare_img()
										snake_case_				:					List[Any]   =       image_processor(images=lowerCAmelCase__       ,							return_tensors="pt"				).to(lowerCAmelCase__				)

										# forward pass
										with torch.no_grad():
													snake_case_				:					Optional[int]   =       model(inputs.pixel_values				)

										# verify outputs
										snake_case_				:					int   =       torch.Size((1, 100, 92)				)
										self.assertEqual(outputs.logits.shape       ,							lowerCAmelCase__				)

										snake_case_				:					str   =       torch.tensor(
										    [[-2_4.0_2_4_8, -1_0.3_0_2_4, -1_4.8_2_9_0], [-4_2.0_3_9_2, -1_6.8_2_0_0, -2_7.4_3_3_4], [-2_7.2_7_4_3, -1_1.8_1_5_4, -1_8.7_1_4_8]]       ,							device=lowerCAmelCase__       ,							)
										snake_case_				:					Optional[int]   =       torch.tensor(
										    [[0.2_5_5_9, 0.5_4_5_5, 0.4_7_0_6], [0.2_9_8_9, 0.7_2_7_9, 0.1_8_7_5], [0.7_7_3_2, 0.4_0_1_7, 0.4_4_6_2]]       ,							device=lowerCAmelCase__				)
										self.assertTrue(torch.allclose(outputs.logits[0, :3, :3]       ,							lowerCAmelCase__       ,							atol=1E-4				)				)
										self.assertTrue(torch.allclose(outputs.pred_boxes[0, :3, :3]       ,							lowerCAmelCase__       ,							atol=1E-4				)				)

										# verify postprocessing
										snake_case_				:					Optional[int]   =       image_processor.post_process_object_detection(
										    lowerCAmelCase__       ,							threshold=0.3       ,							target_sizes=[image.size[::-1]]				)[0]
										snake_case_				:					int   =       torch.tensor([0.9_9_9_4, 0.9_7_9_0, 0.9_9_6_4, 0.9_9_7_2, 0.9_8_6_1]				).to(lowerCAmelCase__				)
										snake_case_				:					List[str]   =       [75, 75, 17, 63, 17]
										snake_case_				:					Tuple   =       torch.tensor([3_3_5.0_6_0_9, 7_9.3_8_4_8, 3_7_5.4_2_1_6, 1_8_7.2_4_9_5]				).to(lowerCAmelCase__				)

										self.assertEqual(len(results["scores"]				)       ,							5				)
										self.assertTrue(torch.allclose(results["scores"]       ,							lowerCAmelCase__       ,							atol=1E-4				)				)
										self.assertSequenceEqual(results["labels"].tolist()       ,							lowerCAmelCase__				)
										self.assertTrue(torch.allclose(results["boxes"][0, :]       ,							lowerCAmelCase__				)				)












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




