


def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : Dict    ):
     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    (      SCREAMING_SNAKE_CASE__      : dict[int, list[int]]    ):
     __UpperCamelCase   							=0
     __UpperCamelCase   							=len(SCREAMING_SNAKE_CASE__    )  # No of vertices in graph
     __UpperCamelCase   							=[0] * n
     __UpperCamelCase   							=[False] * n

     def dfs(SCREAMING_SNAKE_CASE__      : Optional[int]      ,					SCREAMING_SNAKE_CASE__      : Optional[Any]      ,					SCREAMING_SNAKE_CASE__      : Any      ,					SCREAMING_SNAKE_CASE__      : Optional[Any]    ):
          __UpperCamelCase   							=True
          __UpperCamelCase   							=id_
          id_ += 1
          for to in graph[at]:
               if to == parent:
                    pass
               elif not visited[to]:
                    dfs(SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__      ,					id_    )
                    __UpperCamelCase   							=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
                    __UpperCamelCase   							=min(low[at]      ,					low[to]    )

     __UpperCamelCase   							=[]
     for i in range(SCREAMING_SNAKE_CASE__    ):
          if not visited[i]:
               dfs(SCREAMING_SNAKE_CASE__      ,					-1      ,					SCREAMING_SNAKE_CASE__      ,					id_    )
     return bridges


if __name__ == "__main__":
   import doctest

   doctest.testmod()









from __future__ import annotations

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int    ):
     if b == 0:
          return (1, 0)
     ((__UpperCamelCase)							,				(__UpperCamelCase))   							=extended_euclid(SCREAMING_SNAKE_CASE__      ,					a % b    )
     __UpperCamelCase   							=a // b
     return (y, x - k * y)

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int    ):
     ((__UpperCamelCase)							,				(__UpperCamelCase))   							=extended_euclid(SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__    )
     __UpperCamelCase   							=na * na
     __UpperCamelCase   							=ra * x * na + ra * y * na
     return (n % m + m) % m

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int    ):
     ((__UpperCamelCase)							,				(__UpperCamelCase))   							=extended_euclid(SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__    )
     if b < 0:
          __UpperCamelCase   							=(b % n + n) % n
     return b

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int      ,					SCREAMING_SNAKE_CASE__      : int    ):
     __UpperCamelCase							,				__UpperCamelCase   							=invert_modulo(SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__    ), invert_modulo(SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__    )
     __UpperCamelCase   							=na * na
     __UpperCamelCase   							=ra * x * na + ra * y * na
     return (n % m + m) % m


if __name__ == "__main__":
   from doctest import testmod

   testmod(name='chinese_remainder_theorem', verbose=True)
   testmod(name='chinese_remainder_theorem2', verbose=True)
   testmod(name='invert_modulo', verbose=True)
   testmod(name='extended_euclid', verbose=True)





