




'''simple docstring'''



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







class 		lowercase_   :


   """simple docstring"""

   def __init__(   self :     List[Any]   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				{}



   def 							lowerCAmelCase_      (   self :     Union[str, Any]  ,				__lowerCamelCase :     int  ,				__lowerCamelCase :     Tuple  ,				__lowerCamelCase :     Optional[Any]=1   ):

      """simple docstring"""
      if self.graph.get(__lowerCamelCase   ):
         if self.graph[u].count([w, v]   ) == 0:
            self.graph[u].append([w, v]   )
      else:
         _SCREAMING_SNAKE_CASE	=				[[w, v]]
      if not self.graph.get(__lowerCamelCase   ):
         _SCREAMING_SNAKE_CASE	=				[]



   def 							lowerCAmelCase_      (   self :     int   ):

      """simple docstring"""
      return list(self.graph   )



   def 							lowerCAmelCase_      (   self :     Tuple  ,				__lowerCamelCase :     Any  ,				__lowerCamelCase :     Dict   ):

      """simple docstring"""
      if self.graph.get(__lowerCamelCase   ):
         for _ in self.graph[u]:
            if _[1] == v:
               self.graph[u].remove(__lowerCamelCase   )



   def 							lowerCAmelCase_      (   self :     Union[str, Any]  ,				__lowerCamelCase :     str=-2  ,				__lowerCamelCase :     int=-1   ):

      """simple docstring"""
      if s == d:
         return []
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				[]
      if s == -2:
         _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      stack.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				s

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

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

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



   def 							lowerCAmelCase_      (   self :     Optional[Any]  ,				__lowerCamelCase :     Union[str, Any]=-1   ):

      """simple docstring"""
      if c == -1:
         _SCREAMING_SNAKE_CASE	=				floor(random() * 1_0_0_0_0   ) + 1_0
      for i in range(__lowerCamelCase   ):
         # every vertex has max 100 edges
         for _ in range(floor(random() * 1_0_2   ) + 1   ):
            _SCREAMING_SNAKE_CASE	=				floor(random() * c   ) + 1
            if n != i:
               self.add_pair(__lowerCamelCase  ,				__lowerCamelCase  ,				1   )



   def 							lowerCAmelCase_      (   self :     str  ,				__lowerCamelCase :     Any=-2   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				deque()
      _SCREAMING_SNAKE_CASE	=				[]
      if s == -2:
         _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      d.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      while d:
         _SCREAMING_SNAKE_CASE	=				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 							lowerCAmelCase_      (   self :     Tuple  ,				__lowerCamelCase :     List[Any]   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				0
      for x in self.graph:
         for y in self.graph[x]:
            if y[1] == u:
               count += 1
      return count



   def 							lowerCAmelCase_      (   self :     str  ,				__lowerCamelCase :     List[str]   ):

      """simple docstring"""
      return len(self.graph[u]   )



   def 							lowerCAmelCase_      (   self :     List[str]  ,				__lowerCamelCase :     Optional[Any]=-2   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				[]
      if s == -2:
         _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      stack.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				s
      _SCREAMING_SNAKE_CASE	=				[]

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

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

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



   def 							lowerCAmelCase_      (   self :     List[str]   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      stack.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				-2
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				s
      _SCREAMING_SNAKE_CASE	=				False
      _SCREAMING_SNAKE_CASE	=				set()

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

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

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



   def 							lowerCAmelCase_      (   self :     Tuple   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      stack.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				-2
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				s
      _SCREAMING_SNAKE_CASE	=				False
      _SCREAMING_SNAKE_CASE	=				set()

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

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

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



   def 							lowerCAmelCase_      (   self :     Union[str, Any]  ,				__lowerCamelCase :     Union[str, Any]=-2  ,				__lowerCamelCase :     Union[str, Any]=-1   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				time()
      self.dfs(__lowerCamelCase  ,				__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				time()
      return end - begin



   def 							lowerCAmelCase_      (   self :     int  ,				__lowerCamelCase :     Tuple=-2   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				time()
      self.bfs(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				time()
      return end - begin







class 		lowercase_   :


   """simple docstring"""

   def __init__(   self :     Dict   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				{}



   def 							lowerCAmelCase_      (   self :     Union[str, Any]  ,				__lowerCamelCase :     int  ,				__lowerCamelCase :     List[Any]  ,				__lowerCamelCase :     Union[str, Any]=1   ):

      """simple docstring"""
      # 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
         _SCREAMING_SNAKE_CASE	=				[[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
         _SCREAMING_SNAKE_CASE	=				[[w, u]]



   def 							lowerCAmelCase_      (   self :     int  ,				__lowerCamelCase :     Dict  ,				__lowerCamelCase :     List[str]   ):

      """simple docstring"""
      if self.graph.get(__lowerCamelCase   ):
         for _ in self.graph[u]:
            if _[1] == v:
               self.graph[u].remove(__lowerCamelCase   )
        # the other way round
      if self.graph.get(__lowerCamelCase   ):
         for _ in self.graph[v]:
            if _[1] == u:
               self.graph[v].remove(__lowerCamelCase   )



   def 							lowerCAmelCase_      (   self :     List[Any]  ,				__lowerCamelCase :     List[Any]=-2  ,				__lowerCamelCase :     Union[str, Any]=-1   ):

      """simple docstring"""
      if s == d:
         return []
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				[]
      if s == -2:
         _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      stack.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				s

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

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

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



   def 							lowerCAmelCase_      (   self :     Dict  ,				__lowerCamelCase :     Union[str, Any]=-1   ):

      """simple docstring"""
      if c == -1:
         _SCREAMING_SNAKE_CASE	=				floor(random() * 1_0_0_0_0   ) + 1_0
      for i in range(__lowerCamelCase   ):
         # every vertex has max 100 edges
         for _ in range(floor(random() * 1_0_2   ) + 1   ):
            _SCREAMING_SNAKE_CASE	=				floor(random() * c   ) + 1
            if n != i:
               self.add_pair(__lowerCamelCase  ,				__lowerCamelCase  ,				1   )



   def 							lowerCAmelCase_      (   self :     Dict  ,				__lowerCamelCase :     List[Any]=-2   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				deque()
      _SCREAMING_SNAKE_CASE	=				[]
      if s == -2:
         _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      d.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      while d:
         _SCREAMING_SNAKE_CASE	=				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 							lowerCAmelCase_      (   self :     str  ,				__lowerCamelCase :     Tuple   ):

      """simple docstring"""
      return len(self.graph[u]   )



   def 							lowerCAmelCase_      (   self :     str   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      stack.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				-2
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				s
      _SCREAMING_SNAKE_CASE	=				False
      _SCREAMING_SNAKE_CASE	=				set()

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

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

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



   def 							lowerCAmelCase_      (   self :     str   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				list(self.graph   )[0]
      stack.append(__lowerCamelCase   )
      visited.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				-2
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				s
      _SCREAMING_SNAKE_CASE	=				False
      _SCREAMING_SNAKE_CASE	=				set()

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

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

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



   def 							lowerCAmelCase_      (   self :     Optional[Any]   ):

      """simple docstring"""
      return list(self.graph   )



   def 							lowerCAmelCase_      (   self :     str  ,				__lowerCamelCase :     List[str]=-2  ,				__lowerCamelCase :     List[str]=-1   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				time()
      self.dfs(__lowerCamelCase  ,				__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				time()
      return end - begin



   def 							lowerCAmelCase_      (   self :     Optional[Any]  ,				__lowerCamelCase :     Optional[Any]=-2   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				time()
      self.bfs(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				time()
      return end - begin







'''simple docstring'''



# tests directory-specific settings - this file is run automatically
# by pytest before any tests are run

import sys
import warnings
from os.path import abspath, dirname, join


# allow having multiple repository checkouts and not needing to remember to rerun
# 'pip install -e .[dev]' when switching between checkouts and running tests.
lowerCamelCase_			=						abspath(join(dirname(dirname(__file__)), 'src'))
sys.path.insert(1, git_repo_path)

# silence FutureWarning warnings in tests since often we can't act on them until
# they become normal warnings - i.e. the tests still need to test the current functionality
warnings.simplefilter(action='ignore', category=FutureWarning)
def 			SCREAMING_SNAKE_CASE_			(							__A    :			Dict  )			->			Dict:
   from diffusers.utils.testing_utils import pytest_addoption_shared

   pytest_addoption_shared(__A  )






def 			SCREAMING_SNAKE_CASE_			(							__A    :			List[Any]  )			->			str:
   from diffusers.utils.testing_utils import pytest_terminal_summary_main

   _SCREAMING_SNAKE_CASE	=				terminalreporter.config.getoption("--make-reports"  )
   if make_reports:
      pytest_terminal_summary_main(__A	,					id=__A  )

