
"""simple docstring"""


import gc
import random
import tempfile
import unittest

import numpy as np
import torch
from transformers import CLIPTextConfig, CLIPTextModel, CLIPTokenizer

from diffusers import AutoencoderKL, DDIMScheduler, LMSDiscreteScheduler, PNDMScheduler, UNetaDConditionModel
from diffusers.pipelines.stable_diffusion_safe import StableDiffusionPipelineSafe as StableDiffusionPipeline
from diffusers.utils import floats_tensor, nightly, torch_device
from diffusers.utils.testing_utils import require_torch_gpu







class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any      )     ->   Any:
							# clean up the VRAM after each test
							super().tearDown()
							gc.collect()
							torch.cuda.empty_cache()


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]      )     ->   Any:
							A						   =   1
							A						   =   3
							A						   =   (32, 32)

							A						   =   floats_tensor((batch_size, num_channels) + sizes  ,rng=random.Random(0      )      ).to(A_      )
							return image


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   Optional[Any]:
							torch.manual_seed(0      )
							A						   =   UNetaDConditionModel(
							    block_out_channels=(32, 64)  ,layers_per_block=2  ,sample_size=32  ,in_channels=4  ,out_channels=4  ,down_block_types=('DownBlock2D', 'CrossAttnDownBlock2D')  ,up_block_types=('CrossAttnUpBlock2D', 'UpBlock2D')  ,cross_attention_dim=32  ,)
							return model


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Union[str, Any]:
							torch.manual_seed(0      )
							A						   =   AutoencoderKL(
							    block_out_channels=[32, 64]  ,in_channels=3  ,out_channels=3  ,down_block_types=['DownEncoderBlock2D', 'DownEncoderBlock2D']  ,up_block_types=['UpDecoderBlock2D', 'UpDecoderBlock2D']  ,latent_channels=4  ,)
							return model


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   Dict:
							torch.manual_seed(0      )
							A						   =   CLIPTextConfig(
							    bos_token_id=0  ,eos_token_id=2  ,hidden_size=32  ,intermediate_size=37  ,layer_norm_eps=1e-05  ,num_attention_heads=4  ,num_hidden_layers=5  ,pad_token_id=1  ,vocab_size=1000  ,)
							return CLIPTextModel(A_      )


						@property
						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   Optional[Any]:
							def extract(*A_     :      List[str]  ,**A_     :      int      ):







								class 				lowerCAmelCase_				:



														'''simple docstring'''


														def __init__( self     :      Optional[Any]      )     ->   Optional[Any]:
															A						   =   torch.ones([0]      )




														def 						_SCREAMING_SNAKE_CASE      ( self     :      str  ,A_     :      Union[str, Any]      )     ->   int:
															self.pixel_values.to(A_      )
															return self

								return Out()

							return extract


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Dict:
							A						   =   'cpu'  # ensure determinism for the device-dependent torch.Generator
							A						   =   self.dummy_cond_unet
							A						   =   DDIMScheduler(
							    beta_start=0.0_00_85  ,beta_end=0.0_12  ,beta_schedule='scaled_linear'  ,clip_sample=A_  ,set_alpha_to_one=A_  ,)

							A						   =   self.dummy_vae
							A						   =   self.dummy_text_encoder
							A						   =   CLIPTokenizer.from_pretrained('hf-internal-testing/tiny-random-clip'      )

							# make sure here that pndm scheduler skips prk
							A						   =   StableDiffusionPipeline(
							    unet=A_  ,scheduler=A_  ,vae=A_  ,text_encoder=A_  ,tokenizer=A_  ,safety_checker=A_  ,feature_extractor=self.dummy_extractor  ,)
							A						   =   sd_pipe.to(A_      )
							sd_pipe.set_progress_bar_config(disable=A_      )

							A						   =   'A painting of a squirrel eating a burger'

							A						   =   torch.Generator(device=A_      ).manual_seed(0      )
							A						   =   sd_pipe([prompt]  ,generator=A_  ,guidance_scale=6.0  ,num_inference_steps=2  ,output_type='np'      )
							A						   =   output.images

							A						   =   torch.Generator(device=A_      ).manual_seed(0      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=6.0  ,num_inference_steps=2  ,output_type='np'  ,return_dict=A_  ,)[0]

							A						   =   image[0, -3:, -3:, -1]
							A						   =   image_from_tuple[0, -3:, -3:, -1]

							assert image.shape == (1, 64, 64, 3)
							A						   =   np.array([0.57_56, 0.61_18, 0.50_05, 0.50_41, 0.54_71, 0.47_26, 0.49_76, 0.48_65, 0.48_64]      )

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-2
							assert np.abs(image_from_tuple_slice.flatten() - expected_slice      ).max() < 1e-2


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]      )     ->   str:
							A						   =   'cpu'  # ensure determinism for the device-dependent torch.Generator
							A						   =   self.dummy_cond_unet
							A						   =   PNDMScheduler(skip_prk_steps=A_      )
							A						   =   self.dummy_vae
							A						   =   self.dummy_text_encoder
							A						   =   CLIPTokenizer.from_pretrained('hf-internal-testing/tiny-random-clip'      )

							# make sure here that pndm scheduler skips prk
							A						   =   StableDiffusionPipeline(
							    unet=A_  ,scheduler=A_  ,vae=A_  ,text_encoder=A_  ,tokenizer=A_  ,safety_checker=A_  ,feature_extractor=self.dummy_extractor  ,)
							A						   =   sd_pipe.to(A_      )
							sd_pipe.set_progress_bar_config(disable=A_      )

							A						   =   'A painting of a squirrel eating a burger'
							A						   =   torch.Generator(device=A_      ).manual_seed(0      )
							A						   =   sd_pipe([prompt]  ,generator=A_  ,guidance_scale=6.0  ,num_inference_steps=2  ,output_type='np'      )

							A						   =   output.images

							A						   =   torch.Generator(device=A_      ).manual_seed(0      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=6.0  ,num_inference_steps=2  ,output_type='np'  ,return_dict=A_  ,)[0]

							A						   =   image[0, -3:, -3:, -1]
							A						   =   image_from_tuple[0, -3:, -3:, -1]

							assert image.shape == (1, 64, 64, 3)
							A						   =   np.array([0.51_25, 0.57_16, 0.48_28, 0.50_60, 0.56_50, 0.47_68, 0.51_85, 0.48_95, 0.49_93]      )

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-2
							assert np.abs(image_from_tuple_slice.flatten() - expected_slice      ).max() < 1e-2


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Tuple:
							A						   =   StableDiffusionPipeline.from_pretrained(
							    'hf-internal-testing/tiny-stable-diffusion-lms-pipe'  ,safety_checker=A_      )
							assert isinstance(A_  ,A_      )
							assert isinstance(pipe.scheduler  ,A_      )
							assert pipe.safety_checker is None

							A						   =   pipe('example prompt'  ,num_inference_steps=2      ).images[0]
							assert image is not None

							# check that there's no error when saving a pipeline with one of the models being None
							with tempfile.TemporaryDirectory() as tmpdirname:
								pipe.save_pretrained(A_      )
								A						   =   StableDiffusionPipeline.from_pretrained(A_      )

							# sanity check that the pipeline still works
							assert pipe.safety_checker is None
							A						   =   pipe('example prompt'  ,num_inference_steps=2      ).images[0]
							assert image is not None




						@unittest.skipIf(torch_device != 'cuda'  ,'This test requires a GPU'      )
						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   List[str]:
							A						   =   self.dummy_cond_unet
							A						   =   PNDMScheduler(skip_prk_steps=A_      )
							A						   =   self.dummy_vae
							A						   =   self.dummy_text_encoder
							A						   =   CLIPTokenizer.from_pretrained('hf-internal-testing/tiny-random-clip'      )

							# put models in fp16
							A						   =   unet.half()
							A						   =   vae.half()
							A						   =   bert.half()

							# make sure here that pndm scheduler skips prk
							A						   =   StableDiffusionPipeline(
							    unet=A_  ,scheduler=A_  ,vae=A_  ,text_encoder=A_  ,tokenizer=A_  ,safety_checker=A_  ,feature_extractor=self.dummy_extractor  ,)
							A						   =   sd_pipe.to(A_      )
							sd_pipe.set_progress_bar_config(disable=A_      )

							A						   =   'A painting of a squirrel eating a burger'
							A						   =   sd_pipe([prompt]  ,num_inference_steps=2  ,output_type='np'      ).images

							assert image.shape == (1, 64, 64, 3)







@nightly
@require_torch_gpu
class 				lowerCAmelCase_				(      unittest.TestCase    ):



						'''simple docstring'''


						def 						_SCREAMING_SNAKE_CASE      ( self     :      str      )     ->   Tuple:
							# clean up the VRAM after each test
							super().tearDown()
							gc.collect()
							torch.cuda.empty_cache()


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Tuple      )     ->   int:
							A						   =   StableDiffusionPipeline.from_pretrained('runwayml/stable-diffusion-v1-5'  ,safety_checker=A_      )
							A						   =   LMSDiscreteScheduler.from_config(sd_pipe.scheduler.config      )
							A						   =   sd_pipe.to(A_      )
							sd_pipe.set_progress_bar_config(disable=A_      )

							A						   =   (
							    'portrait of girl with smokey eyes makeup in abandoned hotel, grange clothes, redshift, wide high angle'
							    ' coloured polaroid photograph with flash, kodak film, hyper real, stunning moody cinematography, with'
							    ' anamorphic lenses, by maripol, fallen angels by wong kar - wai, style of suspiria and neon demon and'
							    ' children from bahnhof zoo, detailed '
							)
							A						   =   40_0366_0346
							A						   =   7

							# without safety guidance (sld_guidance_scale = 0)
							A						   =   torch.manual_seed(A_      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=A_  ,num_inference_steps=50  ,output_type='np'  ,width=512  ,height=512  ,sld_guidance_scale=0  ,)

							A						   =   output.images
							A						   =   image[0, -3:, -3:, -1]
							A						   =   [0.22_78, 0.22_31, 0.22_49, 0.23_33, 0.23_03, 0.18_85, 0.22_73, 0.21_44, 0.21_76]

							assert image.shape == (1, 512, 512, 3)

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-2

							# without safety guidance (strong configuration)
							A						   =   torch.manual_seed(A_      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=A_  ,num_inference_steps=50  ,output_type='np'  ,width=512  ,height=512  ,sld_guidance_scale=2000  ,sld_warmup_steps=7  ,sld_threshold=0.0_25  ,sld_momentum_scale=0.5  ,sld_mom_beta=0.7  ,)

							A						   =   output.images
							A						   =   image[0, -3:, -3:, -1]
							A						   =   [0.23_83, 0.22_76, 0.2_36, 0.21_92, 0.21_86, 0.20_53, 0.19_71, 0.19_01, 0.17_19]

							assert image.shape == (1, 512, 512, 3)

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-2


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   List[str]:
							A						   =   StableDiffusionPipeline.from_pretrained('runwayml/stable-diffusion-v1-5'  ,safety_checker=A_      )
							A						   =   LMSDiscreteScheduler.from_config(sd_pipe.scheduler.config      )
							A						   =   sd_pipe.to(A_      )
							sd_pipe.set_progress_bar_config(disable=A_      )

							A						   =   'padme amidala taking a bath artwork, safe for work, no nudity'
							A						   =   27_3497_1755
							A						   =   7

							A						   =   torch.manual_seed(A_      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=A_  ,num_inference_steps=50  ,output_type='np'  ,width=512  ,height=512  ,sld_guidance_scale=0  ,)

							A						   =   output.images
							A						   =   image[0, -3:, -3:, -1]
							A						   =   [0.35_02, 0.36_22, 0.33_96, 0.36_42, 0.34_78, 0.33_18, 0.35, 0.33_48, 0.32_97]

							assert image.shape == (1, 512, 512, 3)

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-2

							A						   =   torch.manual_seed(A_      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=A_  ,num_inference_steps=50  ,output_type='np'  ,width=512  ,height=512  ,sld_guidance_scale=2000  ,sld_warmup_steps=7  ,sld_threshold=0.0_25  ,sld_momentum_scale=0.5  ,sld_mom_beta=0.7  ,)

							A						   =   output.images
							A						   =   image[0, -3:, -3:, -1]
							A						   =   [0.55_31, 0.52_06, 0.48_95, 0.51_56, 0.51_82, 0.47_51, 0.48_02, 0.48_03, 0.44_43]

							assert image.shape == (1, 512, 512, 3)

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-2




						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Dict:
							A						   =   StableDiffusionPipeline.from_pretrained('runwayml/stable-diffusion-v1-5'      )
							A						   =   sd_pipe.to(A_      )
							sd_pipe.set_progress_bar_config(disable=A_      )

							A						   =   (
							    'the four horsewomen of the apocalypse, painting by tom of finland, gaston bussiere, craig mullins, j. c.'
							    ' leyendecker'
							)
							A						   =   10_4435_5234
							A						   =   12

							A						   =   torch.manual_seed(A_      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=A_  ,num_inference_steps=50  ,output_type='np'  ,width=512  ,height=512  ,sld_guidance_scale=0  ,)

							A						   =   output.images
							A						   =   image[0, -3:, -3:, -1]
							A						   =   np.array([0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]      )

							assert image.shape == (1, 512, 512, 3)

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-7

							A						   =   torch.manual_seed(A_      )
							A						   =   sd_pipe(
							    [prompt]  ,generator=A_  ,guidance_scale=A_  ,num_inference_steps=50  ,output_type='np'  ,width=512  ,height=512  ,sld_guidance_scale=2000  ,sld_warmup_steps=7  ,sld_threshold=0.0_25  ,sld_momentum_scale=0.5  ,sld_mom_beta=0.7  ,)

							A						   =   output.images
							A						   =   image[0, -3:, -3:, -1]
							A						   =   np.array([0.58_18, 0.62_85, 0.68_35, 0.60_19, 0.6_25, 0.67_54, 0.60_96, 0.63_34, 0.65_61]      )
							assert image.shape == (1, 512, 512, 3)

							assert np.abs(image_slice.flatten() - expected_slice      ).max() < 1e-2

"""simple docstring"""


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







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      Dict      )     ->   int:
							A						   =   {}


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Union[str, Any]  ,A_     :      Any  ,A_     :      Optional[Any]=1      )     ->   int:
							if self.graph.get(A_      ):
								if self.graph[u].count([w, v]      ) == 0:
									self.graph[u].append([w, v]      )
							else:
								A						   =   [[w, v]]
							if not self.graph.get(A_      ):
								A						   =   []


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   Optional[int]:
							return list(self.graph      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Union[str, Any]  ,A_     :      Dict      )     ->   Optional[Any]:
							if self.graph.get(A_      ):
								for _ in self.graph[u]:
									if _[1] == v:
										self.graph[u].remove(A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      int=-2  ,A_     :      Dict=-1      )     ->   str:
							if s == d:
								return []
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   s

							while True:
								# check if there is any non isolated nodes
								if len(self.graph[s]      ) != 0:
									A						   =   s
									for node in self.graph[s]:
										if visited.count(node[1]      ) < 1:
											if node[1] == d:
												visited.append(A_      )
												return visited
											else:
												stack.append(node[1]      )
												visited.append(node[1]      )
												A						   =   node[1]
												break

            # check if all the children are visited
								if s == ss:
									stack.pop()
									if len(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      Any=-1      )     ->   int:
							if c == -1:
								A						   =   floor(random() * 1_0000      ) + 10
							for i in range(A_      ):
								# every vertex has max 100 edges
								for _ in range(floor(random() * 102      ) + 1      ):
									A						   =   floor(random() * c      ) + 1
									if n != i:
										self.add_pair(A_  ,A_  ,1      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      Union[str, Any]=-2      )     ->   Optional[Any]:
							A						   =   deque()
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							d.append(A_      )
							visited.append(A_      )
							while d:
								A						   =   d.popleft()
								if len(self.graph[s]      ) != 0:
									for node in self.graph[s]:
										if visited.count(node[1]      ) < 1:
											d.append(node[1]      )
											visited.append(node[1]      )
							return visited


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Tuple      )     ->   Any:
							A						   =   0
							for x in self.graph:
								for y in self.graph[x]:
									if y[1] == u:
										count += 1
							return count


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,A_     :      Union[str, Any]      )     ->   str:
							return len(self.graph[u]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,A_     :      Union[str, Any]=-2      )     ->   Any:
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   s
							A						   =   []

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

            # check if all the children are visited
								if s == ss:
									sorted_nodes.append(stack.pop()      )
									if len(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]      )     ->   Tuple:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

							while True:
								# check if there is any non isolated nodes
								if len(self.graph[s]      ) != 0:
									A						   =   s
									for node in self.graph[s]:
										if (
										    visited.count(node[1]      ) > 0
										    and node[1] != parent
										    and indirect_parents.count(node[1]      ) > 0
										    and not on_the_way_back
										):
											A						   =   len(A_      ) - 1
											while len_stack >= 0:
												if stack[len_stack] == node[1]:
													anticipating_nodes.add(node[1]      )
													break
												else:
													anticipating_nodes.add(stack[len_stack]      )
													len_stack -= 1
										if visited.count(node[1]      ) < 1:
											stack.append(node[1]      )
											visited.append(node[1]      )
											A						   =   node[1]
											break

            # check if all the children are visited
								if s == ss:
									stack.pop()
									A						   =   True
									if len(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      int      )     ->   Optional[int]:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

							while True:
								# check if there is any non isolated nodes
								if len(self.graph[s]      ) != 0:
									A						   =   s
									for node in self.graph[s]:
										if (
										    visited.count(node[1]      ) > 0
										    and node[1] != parent
										    and indirect_parents.count(node[1]      ) > 0
										    and not on_the_way_back
										):
											A						   =   len(A_      ) - 1
											while len_stack_minus_one >= 0:
												if stack[len_stack_minus_one] == node[1]:
													anticipating_nodes.add(node[1]      )
													break
												else:
													return True
										if visited.count(node[1]      ) < 1:
											stack.append(node[1]      )
											visited.append(node[1]      )
											A						   =   node[1]
											break

            # check if all the children are visited
								if s == ss:
									stack.pop()
									A						   =   True
									if len(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict  ,A_     :      Tuple=-2  ,A_     :      List[str]=-1      )     ->   str:
							A						   =   time()
							self.dfs(A_  ,A_      )
							A						   =   time()
							return end - begin




						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]  ,A_     :      Union[str, Any]=-2      )     ->   Dict:
							A						   =   time()
							self.bfs(A_      )
							A						   =   time()
							return end - begin







class 				lowerCAmelCase_				:



						'''simple docstring'''


						def __init__( self     :      List[Any]      )     ->   Tuple:
							A						   =   {}


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Any  ,A_     :      Optional[Any]  ,A_     :      str  ,A_     :      List[str]=1      )     ->   Dict:
							# check if the u exists
							if self.graph.get(A_      ):
								# if there already is a edge
								if self.graph[u].count([w, v]      ) == 0:
									self.graph[u].append([w, v]      )
							else:
								# if u does not exist
								A						   =   [[w, v]]
							# add the other way
							if self.graph.get(A_      ):
								# if there already is a edge
								if self.graph[v].count([w, u]      ) == 0:
									self.graph[v].append([w, u]      )
							else:
								# if u does not exist
								A						   =   [[w, u]]


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      List[Any]  ,A_     :      List[str]      )     ->   List[Any]:
							if self.graph.get(A_      ):
								for _ in self.graph[u]:
									if _[1] == v:
										self.graph[u].remove(A_      )
        # the other way round
							if self.graph.get(A_      ):
								for _ in self.graph[v]:
									if _[1] == u:
										self.graph[v].remove(A_      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[Any]  ,A_     :      List[str]=-2  ,A_     :      List[Any]=-1      )     ->   int:
							if s == d:
								return []
							A						   =   []
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   s

							while True:
								# check if there is any non isolated nodes
								if len(self.graph[s]      ) != 0:
									A						   =   s
									for node in self.graph[s]:
										if visited.count(node[1]      ) < 1:
											if node[1] == d:
												visited.append(A_      )
												return visited
											else:
												stack.append(node[1]      )
												visited.append(node[1]      )
												A						   =   node[1]
												break

            # check if all the children are visited
								if s == ss:
									stack.pop()
									if len(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[int]=-1      )     ->   List[Any]:
							if c == -1:
								A						   =   floor(random() * 1_0000      ) + 10
							for i in range(A_      ):
								# every vertex has max 100 edges
								for _ in range(floor(random() * 102      ) + 1      ):
									A						   =   floor(random() * c      ) + 1
									if n != i:
										self.add_pair(A_  ,A_  ,1      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      Dict=-2      )     ->   List[Any]:
							A						   =   deque()
							A						   =   []
							if s == -2:
								A						   =   list(self.graph      )[0]
							d.append(A_      )
							visited.append(A_      )
							while d:
								A						   =   d.popleft()
								if len(self.graph[s]      ) != 0:
									for node in self.graph[s]:
										if visited.count(node[1]      ) < 1:
											d.append(node[1]      )
											visited.append(node[1]      )
							return visited


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Union[str, Any]  ,A_     :      Optional[Any]      )     ->   List[Any]:
							return len(self.graph[u]      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      List[str]      )     ->   List[Any]:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

							while True:
								# check if there is any non isolated nodes
								if len(self.graph[s]      ) != 0:
									A						   =   s
									for node in self.graph[s]:
										if (
										    visited.count(node[1]      ) > 0
										    and node[1] != parent
										    and indirect_parents.count(node[1]      ) > 0
										    and not on_the_way_back
										):
											A						   =   len(A_      ) - 1
											while len_stack >= 0:
												if stack[len_stack] == node[1]:
													anticipating_nodes.add(node[1]      )
													break
												else:
													anticipating_nodes.add(stack[len_stack]      )
													len_stack -= 1
										if visited.count(node[1]      ) < 1:
											stack.append(node[1]      )
											visited.append(node[1]      )
											A						   =   node[1]
											break

            # check if all the children are visited
								if s == ss:
									stack.pop()
									A						   =   True
									if len(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]      )     ->   Any:
							A						   =   []
							A						   =   []
							A						   =   list(self.graph      )[0]
							stack.append(A_      )
							visited.append(A_      )
							A						   =   -2
							A						   =   []
							A						   =   s
							A						   =   False
							A						   =   set()

							while True:
								# check if there is any non isolated nodes
								if len(self.graph[s]      ) != 0:
									A						   =   s
									for node in self.graph[s]:
										if (
										    visited.count(node[1]      ) > 0
										    and node[1] != parent
										    and indirect_parents.count(node[1]      ) > 0
										    and not on_the_way_back
										):
											A						   =   len(A_      ) - 1
											while len_stack_minus_one >= 0:
												if stack[len_stack_minus_one] == node[1]:
													anticipating_nodes.add(node[1]      )
													break
												else:
													return True
										if visited.count(node[1]      ) < 1:
											stack.append(node[1]      )
											visited.append(node[1]      )
											A						   =   node[1]
											break

            # check if all the children are visited
								if s == ss:
									stack.pop()
									A						   =   True
									if len(A_      ) != 0:
										A						   =   stack[len(A_      ) - 1]
								else:
									A						   =   False
									indirect_parents.append(A_      )
									A						   =   s
									A						   =   ss

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


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Dict      )     ->   Any:
							return list(self.graph      )


						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[int]  ,A_     :      Optional[Any]=-2  ,A_     :      List[str]=-1      )     ->   Any:
							A						   =   time()
							self.dfs(A_  ,A_      )
							A						   =   time()
							return end - begin




						def 						_SCREAMING_SNAKE_CASE      ( self     :      Optional[Any]  ,A_     :      List[Any]=-2      )     ->   Union[str, Any]:
							A						   =   time()
							self.bfs(A_      )
							A						   =   time()
							return end - begin