





"""simple docstring"""






import unittest

from diffusers.models.unet_ad_blocks import *  # noqa F403
from diffusers.utils import torch_device

from .test_unet_blocks_common import UNetBlockTesterMixin



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  DownBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       def 							__A (   self     ):
              _UpperCAmelCase     =     [-0.0_232, -0.9_869, 0.8_054, -0.0_637, -0.1_688, -1.4_264, 0.4_470, -1.3_394, 0.0_904]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  ResnetDownsampleBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.0_710, 0.2_410, -0.7_320, -1.0_757, -1.1_343, 0.3_540, -0.0_133, -0.2_576, 0.0_948]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  AttnDownBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.0_636, 0.8_964, -0.6_234, -1.0_131, 0.0_844, 0.4_935, 0.3_437, 0.0_911, -0.2_957]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  CrossAttnDownBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       def 							__A (   self     ):
              _UpperCAmelCase    ,							_UpperCAmelCase     =     super().prepare_init_args_and_inputs_for_common()
              _UpperCAmelCase     =     32
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.2_238, -0.7_396, -0.2_255, -0.3_829, 0.1_925, 1.1_665, 0.0_603, -0.7_295, 0.1_983]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  SimpleCrossAttnDownBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_encoder_hidden_states=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase    ,							_UpperCAmelCase     =     super().prepare_init_args_and_inputs_for_common()
              _UpperCAmelCase     =     32
              return init_dict, inputs_dict






       @unittest.skipIf(torch_device == 'mps'    ,  'MPS result is not consistent'     )
       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.7_921, -0.0_992, -0.1_962, -0.7_695, -0.4_242, 0.7_804, 0.4_737, 0.2_765, 0.3_338]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  SkipDownBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_skip_sample=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     [-0.0_845, -0.2_087, -0.2_465, 0.0_971, 0.1_900, -0.0_484, 0.2_664, 0.4_179, 0.5_069]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  AttnSkipDownBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_skip_sample=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.5_539, 0.1_609, 0.4_924, 0.0_537, -0.1_995, 0.4_050, 0.0_979, -0.2_721, -0.0_642]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  DownEncoderBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_temb=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     {
                  'in_channels': 32,
                  'out_channels': 32,
              }
              _UpperCAmelCase     =     self.dummy_input
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [1.1_102, 0.5_302, 0.4_872, -0.0_023, -0.8_042, 0.0_483, -0.3_489, -0.5_632, 0.7_626]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  AttnDownEncoderBlockaD  # noqa F405
       lowerCAmelCase__						 =  """down"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_temb=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     {
                  'in_channels': 32,
                  'out_channels': 32,
              }
              _UpperCAmelCase     =     self.dummy_input
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.8_966, -0.1_486, 0.8_568, 0.8_141, -0.9_046, -0.1_342, -0.0_972, -0.7_417, 0.1_538]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  UNetMidBlockaD  # noqa F405
       lowerCAmelCase__						 =  """mid"""






       def 							__A (   self     ):
              _UpperCAmelCase     =     {
                  'in_channels': 32,
                  'temb_channels': 1_28,
              }
              _UpperCAmelCase     =     self.dummy_input
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [-0.1_062, 1.7_248, 0.3_494, 1.4_569, -0.0_910, -1.2_421, -0.9_984, 0.6_736, 1.0_028]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  UNetMidBlockaDCrossAttn  # noqa F405
       lowerCAmelCase__						 =  """mid"""






       def 							__A (   self     ):
              _UpperCAmelCase    ,							_UpperCAmelCase     =     super().prepare_init_args_and_inputs_for_common()
              _UpperCAmelCase     =     32
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.0_187, 2.4_220, 0.4_484, 1.1_203, -0.6_121, -1.5_122, -0.8_270, 0.7_851, 1.8_335]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  UNetMidBlockaDSimpleCrossAttn  # noqa F405
       lowerCAmelCase__						 =  """mid"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_encoder_hidden_states=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase    ,							_UpperCAmelCase     =     super().prepare_init_args_and_inputs_for_common()
              _UpperCAmelCase     =     32
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.7_143, 1.9_974, 0.5_448, 1.3_977, 0.1_282, -1.1_237, -1.4_238, 0.5_530, 0.8_880]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  UpBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_res_hidden_states_tuple=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     [-0.2_041, -0.4_165, -0.3_022, 0.0_041, -0.6_628, -0.7_053, 0.1_928, -0.0_325, 0.0_523]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  ResnetUpsampleBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_res_hidden_states_tuple=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.2_287, 0.3_549, -0.1_346, 0.4_797, -0.1_715, -0.9_649, 0.7_305, -0.5_864, -0.6_244]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  CrossAttnUpBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_res_hidden_states_tuple=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase    ,							_UpperCAmelCase     =     super().prepare_init_args_and_inputs_for_common()
              _UpperCAmelCase     =     32
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [-0.1_403, -0.3_515, -0.0_420, -0.1_425, 0.3_167, 0.5_094, -0.2_181, 0.5_931, 0.5_582]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  SimpleCrossAttnUpBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_res_hidden_states_tuple=a__    ,  include_encoder_hidden_states=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase    ,							_UpperCAmelCase     =     super().prepare_init_args_and_inputs_for_common()
              _UpperCAmelCase     =     32
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.2_645, 0.1_480, 0.0_909, 0.8_044, -0.9_758, -0.9_083, 0.0_994, -1.1_453, -0.7_402]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  AttnUpBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_res_hidden_states_tuple=a__     )






       @unittest.skipIf(torch_device == 'mps'    ,  'MPS result is not consistent'     )
       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.0_979, 0.1_326, 0.0_021, 0.0_659, 0.2_249, 0.0_059, 0.1_132, 0.5_952, 0.1_033]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  SkipUpBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_res_hidden_states_tuple=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     [-0.0_893, -0.1_234, -0.1_506, -0.0_332, 0.0_123, -0.0_211, 0.0_566, 0.0_143, 0.0_362]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  AttnSkipUpBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_res_hidden_states_tuple=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.0_361, 0.0_617, 0.2_787, -0.0_350, 0.0_342, 0.3_421, -0.0_843, 0.0_913, 0.3_015]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  UpDecoderBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_temb=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     {'in_channels': 32, 'out_channels': 32}

              _UpperCAmelCase     =     self.dummy_input
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.4_404, 0.1_998, -0.9_886, -0.3_320, -0.3_128, -0.7_034, -0.6_955, -0.2_338, -0.3_137]
              super().test_output(a__     )



class 	snake_case					(      snake_case			,	unittest.TestCase							):
       lowerCAmelCase__						 =  AttnUpDecoderBlockaD  # noqa F405
       lowerCAmelCase__						 =  """up"""






       @property
       def 							__A (   self     ):
              return super().get_dummy_input(include_temb=a__     )






       def 							__A (   self     ):
              _UpperCAmelCase     =     {'in_channels': 32, 'out_channels': 32}

              _UpperCAmelCase     =     self.dummy_input
              return init_dict, inputs_dict






       def 							__A (   self     ):
              _UpperCAmelCase     =     [0.6_738, 0.4_491, 0.1_055, 1.0_710, 0.7_316, 0.3_339, 0.3_352, 0.1_023, 0.3_568]
              super().test_output(a__     )













"""simple docstring"""






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



class 	lowerCAmelCase					:






       def __init__(   self     ):
              _UpperCAmelCase     =     {}






       def 							__A (   self    ,  a__    ,  a__    ,  a__=1     ):
              if self.graph.get(a__     ):
                     if self.graph[u].count([w, v]     ) == 0:
                            self.graph[u].append([w, v]     )
              else:
                     _UpperCAmelCase     =     [[w, v]]
              if not self.graph.get(a__     ):
                     _UpperCAmelCase     =     []






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






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






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              if s == d:
                     return []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s

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

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

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






       def 							__A (   self    ,  a__=-1     ):
              if c == -1:
                     _UpperCAmelCase     =     floor(random() * 1_00_00     ) + 10
              for i in range(a__     ):
                     # every vertex has max 100 edges
                     for _ in range(floor(random() * 1_02     ) + 1     ):
                            _UpperCAmelCase     =     floor(random() * c     ) + 1
                            if n != i:
                                   self.add_pair(a__    ,  a__    ,  1     )






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






       def 							__A (   self    ,  a__     ):
              return len(self.graph[u]     )






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              if s == -2:
                     _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     []

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

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

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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              _UpperCAmelCase     =     time()
              self.dfs(a__    ,  a__     )
              _UpperCAmelCase     =     time()
              return end - begin






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     time()
              self.bfs(a__     )
              _UpperCAmelCase     =     time()
              return end - begin



class 	lowerCAmelCase					:






       def __init__(   self     ):
              _UpperCAmelCase     =     {}






       def 							__A (   self    ,  a__    ,  a__    ,  a__=1     ):
              # 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
                     _UpperCAmelCase     =     [[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
                     _UpperCAmelCase     =     [[w, u]]






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

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

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

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






       def 							__A (   self    ,  a__=-1     ):
              if c == -1:
                     _UpperCAmelCase     =     floor(random() * 1_00_00     ) + 10
              for i in range(a__     ):
                     # every vertex has max 100 edges
                     for _ in range(floor(random() * 1_02     ) + 1     ):
                            _UpperCAmelCase     =     floor(random() * c     ) + 1
                            if n != i:
                                   self.add_pair(a__    ,  a__    ,  1     )






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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






       def 							__A (   self     ):
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     list(self.graph     )[0]
              stack.append(a__     )
              visited.append(a__     )
              _UpperCAmelCase     =     -2
              _UpperCAmelCase     =     []
              _UpperCAmelCase     =     s
              _UpperCAmelCase     =     False
              _UpperCAmelCase     =     set()

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

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

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






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






       def 							__A (   self    ,  a__=-2    ,  a__=-1     ):
              _UpperCAmelCase     =     time()
              self.dfs(a__    ,  a__     )
              _UpperCAmelCase     =     time()
              return end - begin






       def 							__A (   self    ,  a__=-2     ):
              _UpperCAmelCase     =     time()
              self.bfs(a__     )
              _UpperCAmelCase     =     time()
              return end - begin






