'''simple docstring'''

import gc
import random
import unittest

import torch

from diffusers import (
    IFImgaImgPipeline,
    IFImgaImgSuperResolutionPipeline,
    IFInpaintingPipeline,
    IFInpaintingSuperResolutionPipeline,
    IFPipeline,
    IFSuperResolutionPipeline,
)
from diffusers.models.attention_processor import AttnAddedKVProcessor
from diffusers.utils.import_utils import is_xformers_available
from diffusers.utils.testing_utils import floats_tensor, load_numpy, require_torch_gpu, skip_mps, slow, torch_device

from ..pipeline_params import TEXT_TO_IMAGE_BATCH_PARAMS, TEXT_TO_IMAGE_PARAMS
from ..test_pipelines_common import PipelineTesterMixin, assert_mean_pixel_difference
from . import IFPipelineTesterMixin


@skip_mps
class     __UpperCAmelCase       ( __a						,       __a						,       unittest.TestCase		):
  __A :				List[str]											= IFPipeline
  __A :				List[str]											= TEXT_TO_IMAGE_PARAMS - {'width', 'height', 'latents'}
  __A :				Union[str, Any]											= TEXT_TO_IMAGE_BATCH_PARAMS
  __A :				Tuple											= PipelineTesterMixin.required_optional_params - {'latents'}





  def 						UpperCAmelCase_	(	self ):
     return self._get_dummy_components()





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase=0 ):
     if str(_lowerCamelCase ).startswith('''mps''' ):
        lowerCAmelCase_			=      torch.manual_seed(_lowerCamelCase )
     else:
        lowerCAmelCase_			=      torch.Generator(device=_lowerCamelCase ).manual_seed(_lowerCamelCase )

     lowerCAmelCase_			=      {
         '''prompt''': '''A painting of a squirrel eating a burger''',
         '''generator''': generator,
         '''num_inference_steps''': 2,
         '''output_type''': '''numpy''',
     }

     return inputs





  def 						UpperCAmelCase_	(	self ):
     self._test_save_load_optional_components()





  @unittest.skipIf(torch_device != '''cuda'''    ,     reason='''float16 requires CUDA''' )
  def 						UpperCAmelCase_	(	self ):
     # Due to non-determinism in save load of the hf-internal-testing/tiny-random-t5 text encoder
     super().test_save_load_floataa(expected_max_diff=1E-1 )





  def 						UpperCAmelCase_	(	self ):
     self._test_attention_slicing_forward_pass(expected_max_diff=1E-2 )





  def 						UpperCAmelCase_	(	self ):
     self._test_save_load_local()





  def 						UpperCAmelCase_	(	self ):
     self._test_inference_batch_single_identical(
         expected_max_diff=1E-2    ,     )







  @unittest.skipIf(
      torch_device != '''cuda''' or not is_xformers_available()    ,     reason='''XFormers attention is only available with CUDA and `xformers` installed'''    ,     )
  def 						UpperCAmelCase_	(	self ):
     self._test_xformers_attention_forwardGenerator_pass(expected_max_diff=1E-3 )






@slow
@require_torch_gpu
class     __UpperCAmelCase       ( unittest.TestCase		):





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





  def 						UpperCAmelCase_	(	self ):
     # if

     lowerCAmelCase_			=      IFPipeline.from_pretrained('''DeepFloyd/IF-I-XL-v1.0'''    ,     variant='''fp16'''    ,     torch_dtype=torch.floataa )

     lowerCAmelCase_			=      IFSuperResolutionPipeline.from_pretrained(
         '''DeepFloyd/IF-II-L-v1.0'''    ,     variant='''fp16'''    ,     torch_dtype=torch.floataa    ,     text_encoder=_lowerCamelCase    ,     tokenizer=_lowerCamelCase )

     # pre compute text embeddings and remove T5 to save memory

     pipe_a.text_encoder.to('''cuda''' )

     lowerCAmelCase_	,lowerCAmelCase_			=      pipe_a.encode_prompt('''anime turtle'''    ,     device='''cuda''' )

     del pipe_a.tokenizer
     del pipe_a.text_encoder
     gc.collect()

     lowerCAmelCase_			=      None
     lowerCAmelCase_			=      None

     pipe_a.enable_model_cpu_offload()
     pipe_a.enable_model_cpu_offload()

     pipe_a.unet.set_attn_processor(AttnAddedKVProcessor() )
     pipe_a.unet.set_attn_processor(AttnAddedKVProcessor() )

     self._test_if(_lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )

     pipe_a.remove_all_hooks()
     pipe_a.remove_all_hooks()

     # img2img

     lowerCAmelCase_			=      IFImgaImgPipeline(**pipe_a.components )
     lowerCAmelCase_			=      IFImgaImgSuperResolutionPipeline(**pipe_a.components )

     pipe_a.enable_model_cpu_offload()
     pipe_a.enable_model_cpu_offload()

     pipe_a.unet.set_attn_processor(AttnAddedKVProcessor() )
     pipe_a.unet.set_attn_processor(AttnAddedKVProcessor() )

     self._test_if_imgaimg(_lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )

     pipe_a.remove_all_hooks()
     pipe_a.remove_all_hooks()

     # inpainting

     lowerCAmelCase_			=      IFInpaintingPipeline(**pipe_a.components )
     lowerCAmelCase_			=      IFInpaintingSuperResolutionPipeline(**pipe_a.components )

     pipe_a.enable_model_cpu_offload()
     pipe_a.enable_model_cpu_offload()

     pipe_a.unet.set_attn_processor(AttnAddedKVProcessor() )
     pipe_a.unet.set_attn_processor(AttnAddedKVProcessor() )

     self._test_if_inpainting(_lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     # pipeline 1

     _start_torch_memory_measurement()

     lowerCAmelCase_			=      torch.Generator(device='''cpu''' ).manual_seed(0 )
     lowerCAmelCase_			=      pipe_a(
         prompt_embeds=_lowerCamelCase    ,     negative_prompt_embeds=_lowerCamelCase    ,     num_inference_steps=2    ,     generator=_lowerCamelCase    ,     output_type='''np'''    ,     )

     lowerCAmelCase_			=      output.images[0]

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

     lowerCAmelCase_			=      torch.cuda.max_memory_allocated()
     assert mem_bytes < 13 * 10**9

     lowerCAmelCase_			=      load_numpy(
         '''https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/if/test_if.npy''' )
     assert_mean_pixel_difference(_lowerCamelCase    ,     _lowerCamelCase )

     # pipeline 2

     _start_torch_memory_measurement()

     lowerCAmelCase_			=      torch.Generator(device='''cpu''' ).manual_seed(0 )

     lowerCAmelCase_			=      floats_tensor((1, 3, 64, 64)    ,     rng=random.Random(0 ) ).to(_lowerCamelCase )

     lowerCAmelCase_			=      pipe_a(
         prompt_embeds=_lowerCamelCase    ,     negative_prompt_embeds=_lowerCamelCase    ,     image=_lowerCamelCase    ,     generator=_lowerCamelCase    ,     num_inference_steps=2    ,     output_type='''np'''    ,     )

     lowerCAmelCase_			=      output.images[0]

     assert image.shape == (256, 256, 3)

     lowerCAmelCase_			=      torch.cuda.max_memory_allocated()
     assert mem_bytes < 4 * 10**9

     lowerCAmelCase_			=      load_numpy(
         '''https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/if/test_if_superresolution_stage_II.npy''' )
     assert_mean_pixel_difference(_lowerCamelCase    ,     _lowerCamelCase )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     # pipeline 1

     _start_torch_memory_measurement()

     lowerCAmelCase_			=      floats_tensor((1, 3, 64, 64)    ,     rng=random.Random(0 ) ).to(_lowerCamelCase )

     lowerCAmelCase_			=      torch.Generator(device='''cpu''' ).manual_seed(0 )

     lowerCAmelCase_			=      pipe_a(
         prompt_embeds=_lowerCamelCase    ,     negative_prompt_embeds=_lowerCamelCase    ,     image=_lowerCamelCase    ,     num_inference_steps=2    ,     generator=_lowerCamelCase    ,     output_type='''np'''    ,     )

     lowerCAmelCase_			=      output.images[0]

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

     lowerCAmelCase_			=      torch.cuda.max_memory_allocated()
     assert mem_bytes < 10 * 10**9

     lowerCAmelCase_			=      load_numpy(
         '''https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/if/test_if_img2img.npy''' )
     assert_mean_pixel_difference(_lowerCamelCase    ,     _lowerCamelCase )

     # pipeline 2

     _start_torch_memory_measurement()

     lowerCAmelCase_			=      torch.Generator(device='''cpu''' ).manual_seed(0 )

     lowerCAmelCase_			=      floats_tensor((1, 3, 256, 256)    ,     rng=random.Random(0 ) ).to(_lowerCamelCase )
     lowerCAmelCase_			=      floats_tensor((1, 3, 64, 64)    ,     rng=random.Random(0 ) ).to(_lowerCamelCase )

     lowerCAmelCase_			=      pipe_a(
         prompt_embeds=_lowerCamelCase    ,     negative_prompt_embeds=_lowerCamelCase    ,     image=_lowerCamelCase    ,     original_image=_lowerCamelCase    ,     generator=_lowerCamelCase    ,     num_inference_steps=2    ,     output_type='''np'''    ,     )

     lowerCAmelCase_			=      output.images[0]

     assert image.shape == (256, 256, 3)

     lowerCAmelCase_			=      torch.cuda.max_memory_allocated()
     assert mem_bytes < 4 * 10**9

     lowerCAmelCase_			=      load_numpy(
         '''https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/if/test_if_img2img_superresolution_stage_II.npy''' )
     assert_mean_pixel_difference(_lowerCamelCase    ,     _lowerCamelCase )







  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     # pipeline 1

     _start_torch_memory_measurement()

     lowerCAmelCase_			=      floats_tensor((1, 3, 64, 64)    ,     rng=random.Random(0 ) ).to(_lowerCamelCase )
     lowerCAmelCase_			=      floats_tensor((1, 3, 64, 64)    ,     rng=random.Random(1 ) ).to(_lowerCamelCase )

     lowerCAmelCase_			=      torch.Generator(device='''cpu''' ).manual_seed(0 )
     lowerCAmelCase_			=      pipe_a(
         prompt_embeds=_lowerCamelCase    ,     negative_prompt_embeds=_lowerCamelCase    ,     image=_lowerCamelCase    ,     mask_image=_lowerCamelCase    ,     num_inference_steps=2    ,     generator=_lowerCamelCase    ,     output_type='''np'''    ,     )

     lowerCAmelCase_			=      output.images[0]

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

     lowerCAmelCase_			=      torch.cuda.max_memory_allocated()
     assert mem_bytes < 10 * 10**9

     lowerCAmelCase_			=      load_numpy(
         '''https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/if/test_if_inpainting.npy''' )
     assert_mean_pixel_difference(_lowerCamelCase    ,     _lowerCamelCase )

     # pipeline 2

     _start_torch_memory_measurement()

     lowerCAmelCase_			=      torch.Generator(device='''cpu''' ).manual_seed(0 )

     lowerCAmelCase_			=      floats_tensor((1, 3, 64, 64)    ,     rng=random.Random(0 ) ).to(_lowerCamelCase )
     lowerCAmelCase_			=      floats_tensor((1, 3, 256, 256)    ,     rng=random.Random(0 ) ).to(_lowerCamelCase )
     lowerCAmelCase_			=      floats_tensor((1, 3, 256, 256)    ,     rng=random.Random(1 ) ).to(_lowerCamelCase )

     lowerCAmelCase_			=      pipe_a(
         prompt_embeds=_lowerCamelCase    ,     negative_prompt_embeds=_lowerCamelCase    ,     image=_lowerCamelCase    ,     mask_image=_lowerCamelCase    ,     original_image=_lowerCamelCase    ,     generator=_lowerCamelCase    ,     num_inference_steps=2    ,     output_type='''np'''    ,     )

     lowerCAmelCase_			=      output.images[0]

     assert image.shape == (256, 256, 3)

     lowerCAmelCase_			=      torch.cuda.max_memory_allocated()
     assert mem_bytes < 4 * 10**9

     lowerCAmelCase_			=      load_numpy(
         '''https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main/if/test_if_inpainting_superresolution_stage_II.npy''' )
     assert_mean_pixel_difference(_lowerCamelCase    ,     _lowerCamelCase )






def snake_case_      (					)			->					List[Any]:
   torch.cuda.empty_cache()
   torch.cuda.reset_max_memory_allocated()
   torch.cuda.reset_peak_memory_stats()






'''simple docstring'''

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


class     __UpperCAmelCase       :





  def __init__(	self ):
     lowerCAmelCase_			=      {}





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase=1 ):
     if self.graph.get(_lowerCamelCase ):
        if self.graph[u].count([w, v] ) == 0:
           self.graph[u].append([w, v] )
     else:
        lowerCAmelCase_			=      [[w, v]]
     if not self.graph.get(_lowerCamelCase ):
        lowerCAmelCase_			=      []





  def 						UpperCAmelCase_	(	self ):
     return list(self.graph )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     if self.graph.get(_lowerCamelCase ):
        for _ in self.graph[u]:
           if _[1] == v:
              self.graph[u].remove(_lowerCamelCase )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     if s == d:
        return []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s

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

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

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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-1 ):
     if c == -1:
        lowerCAmelCase_			=      floor(random() * 1_0000 ) + 10
     for i in range(_lowerCamelCase ):
        # every vertex has max 100 edges
        for _ in range(floor(random() * 102 ) + 1 ):
           lowerCAmelCase_			=      floor(random() * c ) + 1
           if n != i:
              self.add_pair(_lowerCamelCase    ,     _lowerCamelCase    ,     1 )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      deque()
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     d.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     while d:
        lowerCAmelCase_			=      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 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     lowerCAmelCase_			=      0
     for x in self.graph:
        for y in self.graph[x]:
           if y[1] == u:
              count += 1
     return count





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     return len(self.graph[u] )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      []

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

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

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

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

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

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

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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     lowerCAmelCase_			=      time()
     self.dfs(_lowerCamelCase    ,     _lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin







  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      time()
     self.bfs(_lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin






class     __UpperCAmelCase       :





  def __init__(	self ):
     lowerCAmelCase_			=      {}





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase    ,     _lowerCamelCase=1 ):
     # check if the u exists
     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
        lowerCAmelCase_			=      [[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
        lowerCAmelCase_			=      [[w, u]]





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase    ,     _lowerCamelCase ):
     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 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     if s == d:
        return []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      s

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

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

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





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-1 ):
     if c == -1:
        lowerCAmelCase_			=      floor(random() * 1_0000 ) + 10
     for i in range(_lowerCamelCase ):
        # every vertex has max 100 edges
        for _ in range(floor(random() * 102 ) + 1 ):
           lowerCAmelCase_			=      floor(random() * c ) + 1
           if n != i:
              self.add_pair(_lowerCamelCase    ,     _lowerCamelCase    ,     1 )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      deque()
     lowerCAmelCase_			=      []
     if s == -2:
        lowerCAmelCase_			=      list(self.graph )[0]
     d.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     while d:
        lowerCAmelCase_			=      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 						UpperCAmelCase_	(	self    ,     _lowerCamelCase ):
     return len(self.graph[u] )





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

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

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

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





  def 						UpperCAmelCase_	(	self ):
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      list(self.graph )[0]
     stack.append(_lowerCamelCase )
     visited.append(_lowerCamelCase )
     lowerCAmelCase_			=      -2
     lowerCAmelCase_			=      []
     lowerCAmelCase_			=      s
     lowerCAmelCase_			=      False
     lowerCAmelCase_			=      set()

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

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

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





  def 						UpperCAmelCase_	(	self ):
     return list(self.graph )





  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2    ,     _lowerCamelCase=-1 ):
     lowerCAmelCase_			=      time()
     self.dfs(_lowerCamelCase    ,     _lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin







  def 						UpperCAmelCase_	(	self    ,     _lowerCamelCase=-2 ):
     lowerCAmelCase_			=      time()
     self.bfs(_lowerCamelCase )
     lowerCAmelCase_			=      time()
     return end - begin





