




"""simple docstring"""


def    UpperCAmelCase__			(snake_case__				:   int       ):
  """simple docstring"""

  return [
      {
          0: [1, 2],
          1: [0, 2],
          2: [0, 1, 3, 5],
          3: [2, 4],
          4: [3],
          5: [2, 6, 8],
          6: [5, 7],
          7: [6, 8],
          8: [5, 7],
      },
      {
          0: [6],
          1: [9],
          2: [4, 5],
          3: [4],
          4: [2, 3],
          5: [2],
          6: [0, 7],
          7: [6],
          8: [],
          9: [1],
      },
      {
          0: [4],
          1: [6],
          2: [],
          3: [5, 6, 7],
          4: [0, 6],
          5: [3, 8, 9],
          6: [1, 3, 4, 7],
          7: [3, 6, 8, 9],
          8: [5, 7],
          9: [5, 7],
      },
      {
          0: [1, 3],
          1: [0, 2, 4],
          2: [1, 3, 4],
          3: [0, 2, 4],
          4: [1, 2, 3],
      },
  ][index]


def    UpperCAmelCase__			(snake_case__				:   Optional[Any]       ):
  """simple docstring"""

  _snake_case				:						List[str]								=    0
  _snake_case				:						List[Any]								=    len(a__       )  # No of vertices in graph
  _snake_case				:						Optional[int]								=    [0] * n
  _snake_case				:						Tuple								=    [False] * n

  def dfs(snake_case__				:   List[str]						,  snake_case__				:   List[str]						,  snake_case__				:   str						,  snake_case__				:   List[Any]       ):
    _snake_case				:						int								=    True
    _snake_case				:						Dict								=    id_
    id_ += 1
    for to in graph[at]:
      if to == parent:
        pass
      elif not visited[to]:
        dfs(a__						,  a__						,  a__						,  id_       )
        _snake_case				:						Optional[int]								=    min(low[at]						,  low[to]       )
        if id_ <= low[to]:
          bridges.append((at, to) if at < to else (to, at)       )
      else:
        # This edge is a back edge and cannot be a bridge
        _snake_case				:						Optional[int]								=    min(low[at]						,  low[to]       )

  _snake_case				:						Union[str, Any]								=    []
  for i in range(a__       ):
    if not visited[i]:
      dfs(a__						,  -1						,  a__						,  id_       )
  return bridges


if __name__ == "__main__":
     import doctest

     doctest.testmod()



# This code is adapted from OpenAI's release
# https://github.com/openai/human-eval/blob/master/human_eval/execution.py

import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile


def 				lowerCAmelCase__       (			a__    ,     a__    ,     a__    ,     a__ )      ->str:




  '''simple docstring'''

  _UpperCamelCase           =    multiprocessing.Manager()
  _UpperCamelCase           =    manager.list()

  _UpperCamelCase           =    multiprocessing.Process(target=a__    ,     args=(check_program, result, timeout) )
  p.start()
  p.join(timeout=timeout + 1 )
  if p.is_alive():
    p.kill()

  if not result:
    result.append("timed out" )

  return {
      "task_id": task_id,
      "passed": result[0] == "passed",
      "result": result[0],
      "completion_id": completion_id,
  }


def 				lowerCAmelCase__       (			a__    ,     a__    ,     a__ )      ->Union[str, Any]:




  '''simple docstring'''

  with create_tempdir():
    # These system calls are needed when cleaning up tempdir.
    import os
    import shutil

    _UpperCamelCase           =    shutil.rmtree
    _UpperCamelCase           =    os.rmdir
    _UpperCamelCase           =    os.chdir

    # Disable functionalities that can make destructive changes to the test.
    reliability_guard()

    # Run program.
    try:
      _UpperCamelCase           =    {}
      with swallow_io():
        with time_limit(a__ ):
          exec(a__    ,     a__ )
      result.append("passed" )
    except TimeoutException:
      result.append("timed out" )
    except BaseException as e:
      result.append(f'failed: {e}' )

    # Needed for cleaning up.
    _UpperCamelCase           =    rmtree
    _UpperCamelCase           =    rmdir
    _UpperCamelCase           =    chdir


@contextlib.contextmanager
def 				lowerCAmelCase__       (			a__ )      ->Optional[Any]:




  '''simple docstring'''

  def signal_handler(a__    ,     a__ ):
    raise TimeoutException("Timed out!" )

  signal.setitimer(signal.ITIMER_REAL    ,     a__ )
  signal.signal(signal.SIGALRM    ,     a__ )
  try:
    yield
  finally:
    signal.setitimer(signal.ITIMER_REAL    ,     0 )


@contextlib.contextmanager
def 				lowerCAmelCase__       (			)      ->Optional[int]:




  '''simple docstring'''

  _UpperCamelCase           =    WriteOnlyStringIO()
  with contextlib.redirect_stdout(a__ ):
    with contextlib.redirect_stderr(a__ ):
      with redirect_stdin(a__ ):
        yield


@contextlib.contextmanager
def 				lowerCAmelCase__       (			)      ->Optional[int]:




  '''simple docstring'''

  with tempfile.TemporaryDirectory() as dirname:
    with chdir(a__ ):
      yield dirname




class 					_UpperCAmelCase			(     lowerCAmelCase  ):



 '''simple docstring'''




 pass




class 					_UpperCAmelCase			(     io.StringIO  ):



 '''simple docstring'''




 def 		__UpperCAmelCase				(		self				:   List[str]							, *lowercase_				:   str							, **lowercase_				:   List[str])						->	Optional[Any]:


   """simple docstring"""







   raise OSError







 def 		__UpperCAmelCase				(		self				:   Any							, *lowercase_				:   List[Any]							, **lowercase_				:   Optional[int])						->	Optional[int]:


   """simple docstring"""







   raise OSError







 def 		__UpperCAmelCase				(		self				:   int							, *lowercase_				:   int							, **lowercase_				:   str)						->	int:


   """simple docstring"""







   raise OSError







 def 		__UpperCAmelCase				(		self				:   List[Any]							, *lowercase_				:   Tuple							, **lowercase_				:   Tuple)						->	Tuple:


   """simple docstring"""







   return False




class 					_UpperCAmelCase			(     contextlib._RedirectStream  ):  # type: ignore



 '''simple docstring'''




 __A			       =					'''stdin'''


@contextlib.contextmanager
def 				lowerCAmelCase__       (			a__ )      ->str:




  '''simple docstring'''

  if root == ".":
    yield
    return
  _UpperCamelCase           =    os.getcwd()
  os.chdir(a__ )
  try:
    yield
  except BaseException as exc:
    raise exc
  finally:
    os.chdir(a__ )







def 				lowerCAmelCase__       (			a__=None )      ->Optional[int]:




  '''simple docstring'''

  if maximum_memory_bytes is not None:
    import resource

    resource.setrlimit(resource.RLIMIT_AS    ,     (maximum_memory_bytes, maximum_memory_bytes) )
    resource.setrlimit(resource.RLIMIT_DATA    ,     (maximum_memory_bytes, maximum_memory_bytes) )
    if not platform.uname().system == "Darwin":
      resource.setrlimit(resource.RLIMIT_STACK    ,     (maximum_memory_bytes, maximum_memory_bytes) )

  faulthandler.disable()

  import builtins

  _UpperCamelCase           =    None
  _UpperCamelCase           =    None

  import os

  _UpperCamelCase           =    "1"

  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None

  import shutil

  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None

  import subprocess

  _UpperCamelCase           =    None  # type: ignore

  _UpperCamelCase           =    None

  import sys

  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None
  _UpperCamelCase           =    None




