






'''simple docstring'''




import inspect
import unittest

import numpy as np

from tests.test_modeling_common import floats_tensor
from transformers import MaskaFormerConfig, is_torch_available, is_vision_available
from transformers.testing_utils import require_torch, require_torch_multi_gpu, require_vision, slow, torch_device
from transformers.utils import cached_property

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch

		from transformers import MaskaFormerForUniversalSegmentation, MaskaFormerModel

		if is_vision_available():
				from transformers import MaskaFormerImageProcessor

if is_vision_available():
		from PIL import Image







class    A_	:
							"""simple docstring"""




							def __init__(		self			:Tuple       ,							lowerCAmelCase__			:Union[str, Any]       ,							lowerCAmelCase__			:Any=2       ,							lowerCAmelCase__			:Union[str, Any]=True       ,							lowerCAmelCase__			:Dict=False       ,							lowerCAmelCase__			:int=10       ,							lowerCAmelCase__			:Dict=3       ,							lowerCAmelCase__			:Any=32 * 8       ,							lowerCAmelCase__			:Tuple=32 * 8       ,							lowerCAmelCase__			:Optional[int]=4       ,							lowerCAmelCase__			:List[Any]=64       ,							)				->  str:


										'''simple docstring'''




										snake_case_				:					Any   =       parent
										snake_case_				:					Tuple   =       batch_size
										snake_case_				:					Tuple   =       is_training
										snake_case_				:					List[str]   =       use_auxiliary_loss
										snake_case_				:					Dict   =       num_queries
										snake_case_				:					Tuple   =       num_channels
										snake_case_				:					int   =       min_size
										snake_case_				:					str   =       max_size
										snake_case_				:					Optional[int]   =       num_labels
										snake_case_				:					Dict   =       hidden_dim
										snake_case_				:					Optional[int]   =       hidden_dim

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


										'''simple docstring'''




										snake_case_				:					Optional[Any]   =       floats_tensor([self.batch_size, self.num_channels, self.min_size, self.max_size]				).to(
										    lowerCAmelCase__				)

										snake_case_				:					int   =       torch.ones([self.batch_size, self.min_size, self.max_size]       ,							device=lowerCAmelCase__				)

										snake_case_				:					List[Any]   =       (
										    torch.rand([self.batch_size, self.num_labels, self.min_size, self.max_size]       ,							device=lowerCAmelCase__				) > 0.5
										).float()
										snake_case_				:					List[str]   =       (torch.rand((self.batch_size, self.num_labels)       ,							device=lowerCAmelCase__				) > 0.5).long()

										snake_case_				:					str   =       self.get_config()
										return config, pixel_values, pixel_mask, mask_labels, class_labels

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


										'''simple docstring'''




										snake_case_				:					Tuple   =       MaskaFormerConfig(
										    hidden_size=self.hidden_dim       ,							)
										snake_case_				:					List[str]   =       self.num_queries
										snake_case_				:					Dict   =       self.num_labels

										snake_case_				:					Optional[Any]   =       [1, 1, 1, 1]
										snake_case_				:					Any   =       self.num_channels

										snake_case_				:					int   =       64
										snake_case_				:					List[str]   =       128
										snake_case_				:					str   =       self.hidden_dim
										snake_case_				:					int   =       self.hidden_dim
										snake_case_				:					List[str]   =       self.hidden_dim
										return config

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


										'''simple docstring'''




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

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


										'''simple docstring'''




										snake_case_				:					List[str]   =       output.encoder_hidden_states
										snake_case_				:					Optional[Any]   =       output.pixel_decoder_hidden_states
										snake_case_				:					Any   =       output.transformer_decoder_hidden_states

										self.parent.assertTrue(len(lowerCAmelCase__				)       ,							len(config.backbone_config.depths				)				)
										self.parent.assertTrue(len(lowerCAmelCase__				)       ,							len(config.backbone_config.depths				)				)
										self.parent.assertTrue(len(lowerCAmelCase__				)       ,							config.decoder_layers				)

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


										'''simple docstring'''




										with torch.no_grad():
													snake_case_				:					int   =       MaskaFormerModel(config=lowerCAmelCase__				)
													model.to(lowerCAmelCase__				)
													model.eval()

													snake_case_				:					List[Any]   =       model(pixel_values=lowerCAmelCase__       ,							pixel_mask=lowerCAmelCase__				)
													snake_case_				:					Tuple   =       model(lowerCAmelCase__       ,							output_hidden_states=lowerCAmelCase__				)

										self.parent.assertEqual(
										    output.transformer_decoder_last_hidden_state.shape       ,							(self.batch_size, self.num_queries, self.hidden_dim)       ,							)
										# let's ensure the other two hidden state exists
										self.parent.assertTrue(output.pixel_decoder_last_hidden_state is not None				)
										self.parent.assertTrue(output.encoder_last_hidden_state is not None				)

										if output_hidden_states:
													self.check_output_hidden_state(lowerCAmelCase__       ,							lowerCAmelCase__				)






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


										'''simple docstring'''




										snake_case_				:					str   =       MaskaFormerForUniversalSegmentation(config=lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.eval()

										def comm_check_on_output(lowerCAmelCase__			:List[str]				):
													# let's still check that all the required stuff is there
													self.parent.assertTrue(result.transformer_decoder_last_hidden_state is not None				)
													self.parent.assertTrue(result.pixel_decoder_last_hidden_state is not None				)
													self.parent.assertTrue(result.encoder_last_hidden_state is not None				)
													# okay, now we need to check the logits shape
													# due to the encoder compression, masks have a //4 spatial size
													self.parent.assertEqual(
													    result.masks_queries_logits.shape       ,							(self.batch_size, self.num_queries, self.min_size // 4, self.max_size // 4)       ,							)
													# + 1 for null class
													self.parent.assertEqual(
													    result.class_queries_logits.shape       ,							(self.batch_size, self.num_queries, self.num_labels + 1)				)

										with torch.no_grad():
													snake_case_				:					Optional[int]   =       model(pixel_values=lowerCAmelCase__       ,							pixel_mask=lowerCAmelCase__				)
													snake_case_				:					Union[str, Any]   =       model(lowerCAmelCase__				)

													comm_check_on_output(lowerCAmelCase__				)

													snake_case_				:					List[Any]   =       model(
													    pixel_values=lowerCAmelCase__       ,							pixel_mask=lowerCAmelCase__       ,							mask_labels=lowerCAmelCase__       ,							class_labels=lowerCAmelCase__				)

										comm_check_on_output(lowerCAmelCase__				)

										self.parent.assertTrue(result.loss is not None				)
										self.parent.assertEqual(result.loss.shape       ,							torch.Size([1]				)				)







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




							a__   		=	(MaskaFormerModel, MaskaFormerForUniversalSegmentation) if is_torch_available() else ()
							a__   		=	{'feature-extraction': MaskaFormerModel} if is_torch_available() else {}

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

							def 							_A	(		self			:Dict				)				->  Any:


										'''simple docstring'''




										snake_case_				:					Any   =       MaskaFormerModelTester(self				)
										snake_case_				:					str   =       ConfigTester(self       ,							config_class=lowerCAmelCase__       ,							has_text_modality=lowerCAmelCase__				)

							def 							_A	(		self			:int				)				->  Any:


										'''simple docstring'''




										self.config_tester.run_common_tests()

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


										'''simple docstring'''




										snake_case_,	snake_case_				:					Any   =       self.model_tester.prepare_config_and_inputs_for_common()
										self.model_tester.create_and_check_maskaformer_model(lowerCAmelCase__       ,							**lowerCAmelCase__       ,							output_hidden_states=lowerCAmelCase__				)

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


										'''simple docstring'''




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

							@unittest.skip(reason="Mask2Former does not use inputs_embeds"				)
							def 							_A	(		self			:List[Any]				)				->  Optional[Any]:


										'''simple docstring'''




										pass

							@unittest.skip(reason="Mask2Former does not have a get_input_embeddings method"				)
							def 							_A	(		self			:str				)				->  Dict:


										'''simple docstring'''




										pass

							@unittest.skip(reason="Mask2Former is not a generative model"				)
							def 							_A	(		self			:Dict				)				->  int:


										'''simple docstring'''




										pass

							@unittest.skip(reason="Mask2Former does not use token embeddings"				)
							def 							_A	(		self			:List[str]				)				->  List[Any]:


										'''simple docstring'''




										pass

							@require_torch_multi_gpu
							@unittest.skip(
							    reason="Mask2Former has some layers using `add_module` which doesn't work well with `nn.DataParallel`"				)
							def 							_A	(		self			:int				)				->  Any:


										'''simple docstring'''




										pass

							@unittest.skip("Will be fixed soon by reducing the size of the model used for common tests."				)
							def 							_A	(		self			:Dict				)				->  Tuple:


										'''simple docstring'''




										pass

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


										'''simple docstring'''




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

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

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

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


										'''simple docstring'''




										for model_name in ["facebook/mask2former-swin-small-coco-instance"]:
													snake_case_				:					str   =       MaskaFormerModel.from_pretrained(lowerCAmelCase__				)
													self.assertIsNotNone(lowerCAmelCase__				)

							def 							_A	(		self			:Dict				)				->  int:


										'''simple docstring'''




										snake_case_				:					Optional[int]   =       (self.model_tester.min_size,) * 2
										snake_case_				:					int   =       {
										    "pixel_values": torch.randn((2, 3, *size)       ,							device=lowerCAmelCase__				),
										    "mask_labels": torch.randn((2, 10, *size)       ,							device=lowerCAmelCase__				),
										    "class_labels": torch.zeros(2       ,							10       ,							device=lowerCAmelCase__				).long(),
										}
										snake_case_				:					Tuple   =       self.model_tester.get_config()

										snake_case_				:					str   =       MaskaFormerForUniversalSegmentation(lowerCAmelCase__				).to(lowerCAmelCase__				)
										snake_case_				:					Optional[int]   =       model(**lowerCAmelCase__				)
										self.assertTrue(outputs.loss is not None				)

							def 							_A	(		self			:str				)				->  Tuple:


										'''simple docstring'''




										snake_case_,	snake_case_				:					Tuple   =       self.model_tester.prepare_config_and_inputs_for_common()
										self.model_tester.create_and_check_maskaformer_model(lowerCAmelCase__       ,							**lowerCAmelCase__       ,							output_hidden_states=lowerCAmelCase__				)

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


										'''simple docstring'''




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

										for model_class in self.all_model_classes:
													snake_case_				:					Optional[int]   =       model_class(lowerCAmelCase__				).to(lowerCAmelCase__				)
													snake_case_				:					List[Any]   =       model(**lowerCAmelCase__       ,							output_attentions=lowerCAmelCase__				)
													self.assertTrue(outputs.attentions is not None				)

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


										'''simple docstring'''




										if not self.model_tester.is_training:
													return

										snake_case_				:					Optional[Any]   =       self.all_model_classes[1]
										snake_case_,	snake_case_,	snake_case_,	snake_case_,	snake_case_				:					Dict   =       self.model_tester.prepare_config_and_inputs()

										snake_case_				:					str   =       model_class(lowerCAmelCase__				)
										model.to(lowerCAmelCase__				)
										model.train()

										snake_case_				:					str   =       model(lowerCAmelCase__       ,							mask_labels=lowerCAmelCase__       ,							class_labels=lowerCAmelCase__				).loss
										loss.backward()






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


										'''simple docstring'''




										snake_case_				:					List[str]   =       self.all_model_classes[1]
										snake_case_,	snake_case_,	snake_case_,	snake_case_,	snake_case_				:					int   =       self.model_tester.prepare_config_and_inputs()
										snake_case_				:					Dict   =       True
										snake_case_				:					int   =       True

										snake_case_				:					Tuple   =       model_class(lowerCAmelCase__				).to(lowerCAmelCase__				)
										model.train()

										snake_case_				:					Any   =       model(lowerCAmelCase__       ,							mask_labels=lowerCAmelCase__       ,							class_labels=lowerCAmelCase__				)

										snake_case_				:					Optional[Any]   =       outputs.encoder_hidden_states[0]
										encoder_hidden_states.retain_grad()

										snake_case_				:					int   =       outputs.pixel_decoder_hidden_states[0]
										pixel_decoder_hidden_states.retain_grad()

										snake_case_				:					Optional[Any]   =       outputs.transformer_decoder_hidden_states[0]
										transformer_decoder_hidden_states.retain_grad()

										snake_case_				:					Union[str, Any]   =       outputs.attentions[0]
										attentions.retain_grad()

										outputs.loss.backward(retain_graph=lowerCAmelCase__				)

										self.assertIsNotNone(encoder_hidden_states.grad				)
										self.assertIsNotNone(pixel_decoder_hidden_states.grad				)
										self.assertIsNotNone(transformer_decoder_hidden_states.grad				)
										self.assertIsNotNone(attentions.grad				)
__lowerCamelCase   :					int   							=					1E-4

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



			"""simple docstring"""



			snake_case_				:					Optional[int]   =       Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"						)
			return image







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




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


										'''simple docstring'''




										return "facebook/mask2former-swin-small-coco-instance"

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


										'''simple docstring'''




										return MaskaFormerImageProcessor.from_pretrained(self.model_checkpoints				) if is_vision_available() else None

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


										'''simple docstring'''




										snake_case_				:					Any   =       MaskaFormerModel.from_pretrained(self.model_checkpoints				).to(lowerCAmelCase__				)
										snake_case_				:					List[str]   =       self.default_image_processor
										snake_case_				:					Any   =       prepare_img()
										snake_case_				:					Optional[int]   =       image_processor(lowerCAmelCase__       ,							return_tensors="pt"				).to(lowerCAmelCase__				)
										snake_case_				:					int   =       inputs["pixel_values"].shape
										# check size is divisible by 32
										self.assertTrue((inputs_shape[-1] % 32) == 0 and (inputs_shape[-2] % 32) == 0				)
										# check size
										self.assertEqual(lowerCAmelCase__       ,							(1, 3, 384, 384)				)

										with torch.no_grad():
													snake_case_				:					List[Any]   =       model(**lowerCAmelCase__				)

										snake_case_				:					Union[str, Any]   =       torch.tensor(
										    [[-0.2_7_9_0, -1.0_7_1_7, -1.1_6_6_8], [-0.5_1_2_8, -0.3_1_2_8, -0.4_9_8_7], [-0.5_8_3_2, 0.1_9_7_1, -0.0_1_9_7]]				).to(lowerCAmelCase__				)
										self.assertTrue(
										    torch.allclose(
										        outputs.encoder_last_hidden_state[0, 0, :3, :3]       ,							lowerCAmelCase__       ,							atol=lowerCAmelCase__				)				)

										snake_case_				:					List[Any]   =       torch.tensor(
										    [[0.8_9_7_3, 1.1_8_4_7, 1.1_7_7_6], [1.1_9_3_4, 1.5_0_4_0, 1.5_1_2_8], [1.1_1_5_3, 1.4_4_8_6, 1.4_9_5_1]]				).to(lowerCAmelCase__				)
										self.assertTrue(
										    torch.allclose(
										        outputs.pixel_decoder_last_hidden_state[0, 0, :3, :3]       ,							lowerCAmelCase__       ,							atol=lowerCAmelCase__				)				)

										snake_case_				:					List[str]   =       torch.tensor(
										    [[2.1_1_5_2, 1.7_0_0_0, -0.8_6_0_3], [1.5_8_0_8, 1.8_0_0_4, -0.9_3_5_3], [1.6_0_4_3, 1.7_4_9_5, -0.5_9_9_9]]				).to(lowerCAmelCase__				)
										self.assertTrue(
										    torch.allclose(
										        outputs.transformer_decoder_last_hidden_state[0, :3, :3]       ,							lowerCAmelCase__       ,							atol=lowerCAmelCase__				)				)

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


										'''simple docstring'''




										snake_case_				:					int   =       MaskaFormerForUniversalSegmentation.from_pretrained(self.model_checkpoints				).to(lowerCAmelCase__				).eval()
										snake_case_				:					Optional[int]   =       self.default_image_processor
										snake_case_				:					int   =       prepare_img()
										snake_case_				:					Tuple   =       image_processor(lowerCAmelCase__       ,							return_tensors="pt"				).to(lowerCAmelCase__				)
										snake_case_				:					Union[str, Any]   =       inputs["pixel_values"].shape
										# check size is divisible by 32
										self.assertTrue((inputs_shape[-1] % 32) == 0 and (inputs_shape[-2] % 32) == 0				)
										# check size
										self.assertEqual(lowerCAmelCase__       ,							(1, 3, 384, 384)				)

										with torch.no_grad():
													snake_case_				:					Union[str, Any]   =       model(**lowerCAmelCase__				)
										# masks_queries_logits
										snake_case_				:					Optional[Any]   =       outputs.masks_queries_logits
										self.assertEqual(
										    masks_queries_logits.shape       ,							(1, model.config.num_queries, inputs_shape[-2] // 4, inputs_shape[-1] // 4)				)
										snake_case_				:					Optional[Any]   =       [
										    [-8.7_8_3_9, -9.0_0_5_6, -8.8_1_2_1],
										    [-7.4_1_0_4, -7.0_3_1_3, -6.5_4_0_1],
										    [-6.6_1_0_5, -6.3_4_2_7, -6.4_6_7_5],
										]
										snake_case_				:					Any   =       torch.tensor(lowerCAmelCase__				).to(lowerCAmelCase__				)
										self.assertTrue(torch.allclose(masks_queries_logits[0, 0, :3, :3]       ,							lowerCAmelCase__       ,							atol=lowerCAmelCase__				)				)
										# class_queries_logits
										snake_case_				:					Tuple   =       outputs.class_queries_logits
										self.assertEqual(class_queries_logits.shape       ,							(1, model.config.num_queries, model.config.num_labels + 1)				)
										snake_case_				:					Optional[int]   =       torch.tensor(
										    [
										        [1.8_3_2_4, -8.0_8_3_5, -4.1_9_2_2],
										        [0.8_4_5_0, -9.0_0_5_0, -3.6_0_5_3],
										        [0.3_0_4_5, -7.7_2_9_3, -3.0_2_7_5],
										    ]				).to(lowerCAmelCase__				)
										self.assertTrue(torch.allclose(outputs.class_queries_logits[0, :3, :3]       ,							lowerCAmelCase__       ,							atol=lowerCAmelCase__				)				)






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


										'''simple docstring'''




										snake_case_				:					List[str]   =       MaskaFormerForUniversalSegmentation.from_pretrained(self.model_checkpoints				).to(lowerCAmelCase__				).eval()
										snake_case_				:					Optional[int]   =       self.default_image_processor

										snake_case_				:					Dict   =       image_processor(
										    [np.zeros((3, 800, 1_333)				), np.zeros((3, 800, 1_333)				)]       ,							segmentation_maps=[np.zeros((384, 384)				).astype(np.floataa				), np.zeros((384, 384)				).astype(np.floataa				)]       ,							return_tensors="pt"       ,							)

										snake_case_				:					Tuple   =       inputs["pixel_values"].to(lowerCAmelCase__				)
										snake_case_				:					Optional[int]   =       [el.to(lowerCAmelCase__				) for el in inputs["mask_labels"]]
										snake_case_				:					Tuple   =       [el.to(lowerCAmelCase__				) for el in inputs["class_labels"]]

										with torch.no_grad():
													snake_case_				:					Any   =       model(**lowerCAmelCase__				)

										self.assertTrue(outputs.loss is not None				)













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




