


import collections
import os
import re
from pathlib import Path


__lowerCAmelCase			=							'src/transformers'


# Matches is_xxx_available()
__lowerCAmelCase			=							re.compile(r'''is\_([a-z_]*)_available()''')
# Catches a one-line _import_struct = {xxx}
__lowerCAmelCase			=							re.compile(r'''^_import_structure\s+=\s+\{([^\}]+)\}''')
# Catches a line with a key-values pattern: "bla": ["foo", "bar"]
__lowerCAmelCase			=							re.compile(r'''\s+"\S*":\s+\[([^\]]*)\]''')
# Catches a line if not is_foo_available
__lowerCAmelCase			=							re.compile(r'''^\s*if\s+not\s+is\_[a-z_]*\_available\(\)''')
# Catches a line _import_struct["bla"].append("foo")
__lowerCAmelCase			=							re.compile(r'''^\s*_import_structure\["\S*"\]\.append\("(\S*)"\)''')
# Catches a line _import_struct["bla"].extend(["foo", "bar"]) or _import_struct["bla"] = ["foo", "bar"]
__lowerCAmelCase			=							re.compile(r'''^\s*_import_structure\[\S*\](?:\.extend\(|\s*=\s+)\[([^\]]*)\]''')
# Catches a line with an object between quotes and a comma:     "MyModel",
__lowerCAmelCase			=							re.compile(r'''^\s+"([^"]+)",''')
# Catches a line with objects between brackets only:    ["foo", "bar"],
__lowerCAmelCase			=							re.compile(r'''^\s+\[([^\]]+)\]''')
# Catches a line with from foo import bar, bla, boo
__lowerCAmelCase			=							re.compile(r'''\s+from\s+\S*\s+import\s+([^\(\s].*)\n''')
# Catches a line with try:
__lowerCAmelCase			=							re.compile(r'''^\s*try:''')
# Catches a line with else:
__lowerCAmelCase			=							re.compile(r'''^\s*else:''')




def        snake_case_					(  snake_case					)  ->    List[str]:


       if _re_test_backend.search(lowerCAmelCase__					) is None:
              return None
       lowercase__:       Any        =       [b[0] for b in _re_backend.findall(lowerCAmelCase__					)]
       backends.sort()
       return "_and_".join(lowerCAmelCase__					)




def        snake_case_					(  snake_case					)  ->    List[str]:


       with open(lowerCAmelCase__      ,							'r'      ,							encoding='utf-8'      ,							newline='\n'					) as f:
              lowercase__:       Optional[int]        =       f.readlines()

       lowercase__:       int        =       0
       while line_index < len(lowerCAmelCase__					) and not lines[line_index].startswith('_import_structure = {'					):
              line_index += 1

       # If this is a traditional init, just return.
       if line_index >= len(lowerCAmelCase__					):
              return None

       # First grab the objects without a specific backend in _import_structure
       lowercase__:       Optional[int]        =       []
       while not lines[line_index].startswith('if TYPE_CHECKING'					) and find_backend(lines[line_index]					) is None:
              lowercase__:       List[Any]        =       lines[line_index]
              # If we have everything on a single line, let's deal with it.
              if _re_one_line_import_struct.search(lowerCAmelCase__					):
                     lowercase__:       Optional[int]        =       _re_one_line_import_struct.search(lowerCAmelCase__					).groups()[0]
                     lowercase__:       Union[str, Any]        =       re.findall(R'\[([^\]]+)\]'      ,							lowerCAmelCase__					)
                     for imp in imports:
                            objects.extend([obj[1:-1] for obj in imp.split(', '					)]					)
                     line_index += 1
                     continue
              lowercase__:       int        =       _re_import_struct_key_value.search(lowerCAmelCase__					)
              if single_line_import_search is not None:
                     lowercase__:       str        =       [obj[1:-1] for obj in single_line_import_search.groups()[0].split(', '					) if len(lowerCAmelCase__					) > 0]
                     objects.extend(lowerCAmelCase__					)
              elif line.startswith(' ' * 8 + '\"'					):
                     objects.append(line[9:-3]					)
              line_index += 1

       lowercase__:       Any        =       {"""none""": objects}
       # Let's continue with backend-specific objects in _import_structure
       while not lines[line_index].startswith('if TYPE_CHECKING'					):
              # If the line is an if not is_backend_available, we grab all objects associated.
              lowercase__:       Optional[int]        =       find_backend(lines[line_index]					)
              # Check if the backend declaration is inside a try block:
              if _re_try.search(lines[line_index - 1]					) is None:
                     lowercase__:       Tuple        =       None

              if backend is not None:
                     line_index += 1

                     # Scroll until we hit the else block of try-except-else
                     while _re_else.search(lines[line_index]					) is None:
                            line_index += 1

                     line_index += 1

                     lowercase__:       Dict        =       []
                     # Until we unindent, add backend objects to the list
                     while len(lines[line_index]					) <= 1 or lines[line_index].startswith(' ' * 4					):
                            lowercase__:       int        =       lines[line_index]
                            if _re_import_struct_add_one.search(lowerCAmelCase__					) is not None:
                                   objects.append(_re_import_struct_add_one.search(lowerCAmelCase__					).groups()[0]					)
                            elif _re_import_struct_add_many.search(lowerCAmelCase__					) is not None:
                                   lowercase__:       Optional[Any]        =       _re_import_struct_add_many.search(lowerCAmelCase__					).groups()[0].split(', '					)
                                   lowercase__:       int        =       [obj[1:-1] for obj in imports if len(lowerCAmelCase__					) > 0]
                                   objects.extend(lowerCAmelCase__					)
                            elif _re_between_brackets.search(lowerCAmelCase__					) is not None:
                                   lowercase__:       Optional[Any]        =       _re_between_brackets.search(lowerCAmelCase__					).groups()[0].split(', '					)
                                   lowercase__:       List[Any]        =       [obj[1:-1] for obj in imports if len(lowerCAmelCase__					) > 0]
                                   objects.extend(lowerCAmelCase__					)
                            elif _re_quote_object.search(lowerCAmelCase__					) is not None:
                                   objects.append(_re_quote_object.search(lowerCAmelCase__					).groups()[0]					)
                            elif line.startswith(' ' * 8 + '\"'					):
                                   objects.append(line[9:-3]					)
                            elif line.startswith(' ' * 12 + '\"'					):
                                   objects.append(line[13:-3]					)
                            line_index += 1

                     lowercase__:       List[Any]        =       objects
              else:
                     line_index += 1

    # At this stage we are in the TYPE_CHECKING part, first grab the objects without a specific backend
       lowercase__:       Optional[Any]        =       []
       while (
           line_index < len(lowerCAmelCase__					)
           and find_backend(lines[line_index]					) is None
           and not lines[line_index].startswith('else'					)
       ):
              lowercase__:       int        =       lines[line_index]
              lowercase__:       Any        =       _re_import.search(lowerCAmelCase__					)
              if single_line_import_search is not None:
                     objects.extend(single_line_import_search.groups()[0].split(', '					)					)
              elif line.startswith(' ' * 8					):
                     objects.append(line[8:-2]					)
              line_index += 1

       lowercase__:       str        =       {"""none""": objects}
       # Let's continue with backend-specific objects
       while line_index < len(lowerCAmelCase__					):
              # If the line is an if is_backend_available, we grab all objects associated.
              lowercase__:       Tuple        =       find_backend(lines[line_index]					)
              # Check if the backend declaration is inside a try block:
              if _re_try.search(lines[line_index - 1]					) is None:
                     lowercase__:       Dict        =       None

              if backend is not None:
                     line_index += 1

                     # Scroll until we hit the else block of try-except-else
                     while _re_else.search(lines[line_index]					) is None:
                            line_index += 1

                     line_index += 1

                     lowercase__:       List[str]        =       []
                     # Until we unindent, add backend objects to the list
                     while len(lines[line_index]					) <= 1 or lines[line_index].startswith(' ' * 8					):
                            lowercase__:       int        =       lines[line_index]
                            lowercase__:       Tuple        =       _re_import.search(lowerCAmelCase__					)
                            if single_line_import_search is not None:
                                   objects.extend(single_line_import_search.groups()[0].split(', '					)					)
                            elif line.startswith(' ' * 12					):
                                   objects.append(line[12:-2]					)
                            line_index += 1

                     lowercase__:       Optional[Any]        =       objects
              else:
                     line_index += 1

       return import_dict_objects, type_hint_objects




def        snake_case_					(  snake_case      ,							snake_case					)  ->    Tuple:


       def find_duplicates(snake_case					):
              return [k for k, v in collections.Counter(lowerCAmelCase__					).items() if v > 1]

       if list(import_dict_objects.keys()					) != list(type_hint_objects.keys()					):
              return ["Both sides of the init do not have the same backends!"]

       lowercase__:       str        =       []
       for key in import_dict_objects.keys():
              lowercase__:       Any        =       find_duplicates(import_dict_objects[key]					)
              if duplicate_imports:
                     errors.append(f'Duplicate _import_structure definitions for: {duplicate_imports}'					)
              lowercase__:       Optional[Any]        =       find_duplicates(type_hint_objects[key]					)
              if duplicate_type_hints:
                     errors.append(f'Duplicate TYPE_CHECKING objects for: {duplicate_type_hints}'					)

              if sorted(set(import_dict_objects[key]					)					) != sorted(set(type_hint_objects[key]					)					):
                     lowercase__:       Union[str, Any]        =       """base imports""" if key == """none""" else f'{key} backend'
                     errors.append(f'Differences for {name}:'					)
                     for a in type_hint_objects[key]:
                            if a not in import_dict_objects[key]:
                                   errors.append(f'  {a} in TYPE_HINT but not in _import_structure.'					)
                     for a in import_dict_objects[key]:
                            if a not in type_hint_objects[key]:
                                   errors.append(f'  {a} in _import_structure but not in TYPE_HINT.'					)
       return errors




def        snake_case_					(  )  ->    Tuple:
       lowercase__:       Tuple        =       []
       for root, _, files in os.walk(lowerCAmelCase__					):
              if "__init__.py" in files:
                     lowercase__:       List[Any]        =       os.path.join(lowerCAmelCase__      ,							'__init__.py'					)
                     lowercase__:       Any        =       parse_init(lowerCAmelCase__					)
                     if objects is not None:
                            lowercase__:       Union[str, Any]        =       analyze_results(*lowerCAmelCase__					)
                            if len(lowerCAmelCase__					) > 0:
                                   lowercase__:       int        =       f'Problem in {fname}, both halves do not define the same objects.\n{errors[0]}'
                                   failures.append('\n'.join(lowerCAmelCase__					)					)
       if len(lowerCAmelCase__					) > 0:
              raise ValueError('\n\n'.join(lowerCAmelCase__					)					)




def        snake_case_					(  )  ->    Optional[int]:
       lowercase__:       Union[str, Any]        =       []
       for path, directories, files in os.walk(lowerCAmelCase__					):
              for folder in directories:
                     # Ignore private modules
                     if folder.startswith('_'					):
                            directories.remove(lowerCAmelCase__					)
                            continue
                     # Ignore leftovers from branches (empty folders apart from pycache)
                     if len(list((Path(lowerCAmelCase__					) / folder).glob('*.py'					)					)					) == 0:
                            continue
                     lowercase__:       Any        =       str((Path(lowerCAmelCase__					) / folder).relative_to(lowerCAmelCase__					)					)
                     lowercase__:       Union[str, Any]        =       short_path.replace(os.path.sep      ,							'.'					)
                     submodules.append(lowerCAmelCase__					)
              for fname in files:
                     if fname == "__init__.py":
                            continue
                     lowercase__:       Optional[Any]        =       str((Path(lowerCAmelCase__					) / fname).relative_to(lowerCAmelCase__					)					)
                     lowercase__:       Dict        =       short_path.replace('.py'      ,							''					).replace(os.path.sep      ,							'.'					)
                     if len(submodule.split('.'					)					) == 1:
                            submodules.append(lowerCAmelCase__					)
       return submodules


__lowerCAmelCase			=							[
    'convert_pytorch_checkpoint_to_tf2',
    'modeling_flax_pytorch_utils',
    'models.esm.openfold_utils',
]




def        snake_case_					(  )  ->    Optional[Any]:
       from transformers.utils import direct_transformers_import

       lowercase__:       Union[str, Any]        =       direct_transformers_import(lowerCAmelCase__					)

       lowercase__:       List[str]        =       set(transformers._import_structure.keys()					)
       # This contains all the base keys of the _import_structure object defined in the init, but if the user is missing
       # some optional dependencies, they may not have all of them. Thus we read the init to read all additions and
       # (potentiall re-) add them.
       with open(os.path.join(lowerCAmelCase__      ,							'__init__.py'					)      ,							'r'					) as f:
              lowercase__:       Optional[Any]        =       f.read()
       import_structure_keys.update(set(re.findall(R'import_structure\[\"([^\"]*)\"\]'      ,							lowerCAmelCase__					)					)					)

       lowercase__:       List[str]        =       [
           module
           for module in get_transformers_submodules()
           if module not in IGNORE_SUBMODULES and module not in import_structure_keys
       ]

       if len(lowerCAmelCase__					) > 0:
              lowercase__:       str        =       """\n""".join(f'- {module}' for module in module_not_registered					)
              raise ValueError(
                  'The following submodules are not properly registed in the main init of Transformers:\n'
                  f'{list_of_modules}\n'
                  'Make sure they appear somewhere in the keys of `_import_structure` with an empty list as value.'					)


if __name__ == "__main__":
 check_all_inits()
 check_submodules()




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





class   __a      :
 def __init__(       self			) ->    Dict:




        '''simple docstring'''
        lowercase__:       Dict        =       {}
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__    ,			lowerCAmelCase__=1			) ->    Optional[int]:




        '''simple docstring'''
        if self.graph.get(lowerCAmelCase__			):
               if self.graph[u].count([w, v]			) == 0:
                      self.graph[u].append([w, v]			)
        else:
               lowercase__:       int        =       [[w, v]]
        if not self.graph.get(lowerCAmelCase__			):
               lowercase__:       Union[str, Any]        =       []
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Any:




        '''simple docstring'''
        return list(self.graph			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__			) ->    Optional[int]:




        '''simple docstring'''
        if self.graph.get(lowerCAmelCase__			):
               for _ in self.graph[u]:
                      if _[1] == v:
                             self.graph[u].remove(lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    Union[str, Any]:




        '''simple docstring'''
        if s == d:
               return []
        lowercase__:       Tuple        =       []
        lowercase__:       Tuple        =       []
        if s == -2:
               lowercase__:       Any        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Dict        =       s

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

            # check if all the children are visited
               if s == ss:
                      stack.pop()
                      if len(lowerCAmelCase__			) != 0:
                             lowercase__:       Optional[int]        =       stack[len(lowerCAmelCase__			) - 1]
               else:
                      lowercase__:       Dict        =       ss

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return visited
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-1			) ->    List[str]:




        '''simple docstring'''
        if c == -1:
               lowercase__:       int        =       floor(random() * 10_000			) + 10
        for i in range(lowerCAmelCase__			):
               # every vertex has max 100 edges
               for _ in range(floor(random() * 102			) + 1			):
                      lowercase__:       str        =       floor(random() * c			) + 1
                      if n != i:
                             self.add_pair(lowerCAmelCase__    ,			lowerCAmelCase__    ,			1			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    Dict:




        '''simple docstring'''
        lowercase__:       int        =       deque()
        lowercase__:       Dict        =       []
        if s == -2:
               lowercase__:       Optional[int]        =       list(self.graph			)[0]
        d.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        while d:
               lowercase__:       str        =       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    ,			lowerCAmelCase__			) ->    Dict:




        '''simple docstring'''
        lowercase__:       Tuple        =       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    ,			lowerCAmelCase__			) ->    Union[str, Any]:




        '''simple docstring'''
        return len(self.graph[u]			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    Optional[Any]:




        '''simple docstring'''
        lowercase__:       Tuple        =       []
        lowercase__:       str        =       []
        if s == -2:
               lowercase__:       Dict        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       List[Any]        =       s
        lowercase__:       Any        =       []

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

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return sorted_nodes
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Any:




        '''simple docstring'''
        lowercase__:       List[Any]        =       []
        lowercase__:       int        =       []
        lowercase__:       List[str]        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Dict        =       -2
        lowercase__:       Union[str, Any]        =       []
        lowercase__:       List[str]        =       s
        lowercase__:       Dict        =       False
        lowercase__:       Union[str, Any]        =       set()

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

            # check if all the children are visited
               if s == ss:
                      stack.pop()
                      lowercase__:       Any        =       True
                      if len(lowerCAmelCase__			) != 0:
                             lowercase__:       Optional[Any]        =       stack[len(lowerCAmelCase__			) - 1]
               else:
                      lowercase__:       Union[str, Any]        =       False
                      indirect_parents.append(lowerCAmelCase__			)
                      lowercase__:       int        =       s
                      lowercase__:       str        =       ss

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return list(lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Optional[Any]:




        '''simple docstring'''
        lowercase__:       Any        =       []
        lowercase__:       int        =       []
        lowercase__:       Dict        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Optional[int]        =       -2
        lowercase__:       List[Any]        =       []
        lowercase__:       List[str]        =       s
        lowercase__:       List[Any]        =       False
        lowercase__:       str        =       set()

        while True:
               # check if there is any non isolated nodes
               if len(self.graph[s]			) != 0:
                      lowercase__:       Dict        =       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
                             ):
                                    lowercase__:       Any        =       len(lowerCAmelCase__			) - 1
                                    while len_stack_minus_one >= 0:
                                           if stack[len_stack_minus_one] == node[1]:
                                                  anticipating_nodes.add(node[1]			)
                                                  break
                                           else:
                                                  return True
                             if visited.count(node[1]			) < 1:
                                    stack.append(node[1]			)
                                    visited.append(node[1]			)
                                    lowercase__:       List[Any]        =       node[1]
                                    break

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

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return False
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    Dict:




        '''simple docstring'''
        lowercase__:       Union[str, Any]        =       time()
        self.dfs(lowerCAmelCase__    ,			lowerCAmelCase__			)
        lowercase__:       Optional[Any]        =       time()
        return end - begin
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    List[str]:




        '''simple docstring'''
        lowercase__:       str        =       time()
        self.bfs(lowerCAmelCase__			)
        lowercase__:       List[str]        =       time()
        return end - begin





class   __a      :
 def __init__(       self			) ->    Tuple:




        '''simple docstring'''
        lowercase__:       Dict        =       {}
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__    ,			lowerCAmelCase__=1			) ->    List[Any]:




        '''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
               lowercase__:       str        =       [[w, v]]
        # add the other way
        if self.graph.get(lowerCAmelCase__			):
               # if there already is a edge
               if self.graph[v].count([w, u]			) == 0:
                      self.graph[v].append([w, u]			)
        else:
               # if u does not exist
               lowercase__:       Union[str, Any]        =       [[w, u]]
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__    ,			lowerCAmelCase__			) ->    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 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    List[str]:




        '''simple docstring'''
        if s == d:
               return []
        lowercase__:       str        =       []
        lowercase__:       int        =       []
        if s == -2:
               lowercase__:       Tuple        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       int        =       s

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

            # check if all the children are visited
               if s == ss:
                      stack.pop()
                      if len(lowerCAmelCase__			) != 0:
                             lowercase__:       Union[str, Any]        =       stack[len(lowerCAmelCase__			) - 1]
               else:
                      lowercase__:       Optional[Any]        =       ss

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return visited
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-1			) ->    Optional[Any]:




        '''simple docstring'''
        if c == -1:
               lowercase__:       Any        =       floor(random() * 10_000			) + 10
        for i in range(lowerCAmelCase__			):
               # every vertex has max 100 edges
               for _ in range(floor(random() * 102			) + 1			):
                      lowercase__:       Optional[Any]        =       floor(random() * c			) + 1
                      if n != i:
                             self.add_pair(lowerCAmelCase__    ,			lowerCAmelCase__    ,			1			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    List[Any]:




        '''simple docstring'''
        lowercase__:       str        =       deque()
        lowercase__:       List[Any]        =       []
        if s == -2:
               lowercase__:       str        =       list(self.graph			)[0]
        d.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        while d:
               lowercase__:       Union[str, Any]        =       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    ,			lowerCAmelCase__			) ->    List[Any]:




        '''simple docstring'''
        return len(self.graph[u]			)
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    str:




        '''simple docstring'''
        lowercase__:       str        =       []
        lowercase__:       Dict        =       []
        lowercase__:       Optional[int]        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Dict        =       -2
        lowercase__:       Dict        =       []
        lowercase__:       List[Any]        =       s
        lowercase__:       Union[str, Any]        =       False
        lowercase__:       List[str]        =       set()

        while True:
               # check if there is any non isolated nodes
               if len(self.graph[s]			) != 0:
                      lowercase__:       Optional[int]        =       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
                             ):
                                    lowercase__:       Any        =       len(lowerCAmelCase__			) - 1
                                    while len_stack >= 0:
                                           if stack[len_stack] == node[1]:
                                                  anticipating_nodes.add(node[1]			)
                                                  break
                                           else:
                                                  anticipating_nodes.add(stack[len_stack]			)
                                                  len_stack -= 1
                             if visited.count(node[1]			) < 1:
                                    stack.append(node[1]			)
                                    visited.append(node[1]			)
                                    lowercase__:       List[str]        =       node[1]
                                    break

            # check if all the children are visited
               if s == ss:
                      stack.pop()
                      lowercase__:       str        =       True
                      if len(lowerCAmelCase__			) != 0:
                             lowercase__:       Dict        =       stack[len(lowerCAmelCase__			) - 1]
               else:
                      lowercase__:       int        =       False
                      indirect_parents.append(lowerCAmelCase__			)
                      lowercase__:       Tuple        =       s
                      lowercase__:       List[Any]        =       ss

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return list(lowerCAmelCase__			)
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    Any:




        '''simple docstring'''
        lowercase__:       Tuple        =       []
        lowercase__:       Optional[int]        =       []
        lowercase__:       Optional[Any]        =       list(self.graph			)[0]
        stack.append(lowerCAmelCase__			)
        visited.append(lowerCAmelCase__			)
        lowercase__:       Tuple        =       -2
        lowercase__:       Any        =       []
        lowercase__:       int        =       s
        lowercase__:       Optional[int]        =       False
        lowercase__:       List[Any]        =       set()

        while True:
               # check if there is any non isolated nodes
               if len(self.graph[s]			) != 0:
                      lowercase__:       Optional[int]        =       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
                             ):
                                    lowercase__:       Union[str, Any]        =       len(lowerCAmelCase__			) - 1
                                    while len_stack_minus_one >= 0:
                                           if stack[len_stack_minus_one] == node[1]:
                                                  anticipating_nodes.add(node[1]			)
                                                  break
                                           else:
                                                  return True
                             if visited.count(node[1]			) < 1:
                                    stack.append(node[1]			)
                                    visited.append(node[1]			)
                                    lowercase__:       Any        =       node[1]
                                    break

            # check if all the children are visited
               if s == ss:
                      stack.pop()
                      lowercase__:       List[str]        =       True
                      if len(lowerCAmelCase__			) != 0:
                             lowercase__:       List[str]        =       stack[len(lowerCAmelCase__			) - 1]
               else:
                      lowercase__:       Dict        =       False
                      indirect_parents.append(lowerCAmelCase__			)
                      lowercase__:       Optional[Any]        =       s
                      lowercase__:       Optional[int]        =       ss

               # check if se have reached the starting point
               if len(lowerCAmelCase__			) == 0:
                      return False
 def 		SCREAMING_SNAKE_CASE__       (       self			) ->    List[Any]:




        '''simple docstring'''
        return list(self.graph			)
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2    ,			lowerCAmelCase__=-1			) ->    Union[str, Any]:




        '''simple docstring'''
        lowercase__:       Dict        =       time()
        self.dfs(lowerCAmelCase__    ,			lowerCAmelCase__			)
        lowercase__:       List[Any]        =       time()
        return end - begin
 def 		SCREAMING_SNAKE_CASE__       (       self    ,			lowerCAmelCase__=-2			) ->    List[Any]:




        '''simple docstring'''
        lowercase__:       str        =       time()
        self.bfs(lowerCAmelCase__			)
        lowercase__:       List[str]        =       time()
        return end - begin


