






'''simple docstring'''
def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    str           =						len(A__							) + 1
   lowercase_	:    Tuple           =						len(A__							) + 1

   # dp is a 2d matrix where dp[i][j] denotes whether prefix string of
   # length i of input_string matches with prefix string of length j of
   # given pattern.
   # "dp" stands for dynamic programming.
   lowercase_	:    List[Any]           =						[[0 for i in range(A__							)] for j in range(A__							)]

   # since string of zero length match pattern of zero length
   lowercase_	:    str           =						1

   # since pattern of zero length will never match with string of non-zero length
   for i in range(1						,		A__							):
      lowercase_	:    Tuple           =						0

   # since string of zero length will match with pattern where there
   # is at least one * alternatively
   for j in range(1						,		A__							):
      lowercase_	:    str           =						dp[0][j - 2] if pattern[j - 1] == "*" else 0

   # now using bottom-up approach to find for all remaining lengths
   for i in range(1						,		A__							):
      for j in range(1						,		A__							):
         if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
            lowercase_	:    Any           =						dp[i - 1][j - 1]

         elif pattern[j - 1] == "*":
            if dp[i][j - 2] == 1:
               lowercase_	:    List[Any]           =						1
            elif pattern[j - 2] in (input_string[i - 1], "."):
               lowercase_	:    int           =						dp[i - 1][j]
            else:
               lowercase_	:    Dict           =						0
         else:
            lowercase_	:    int           =						0

   return bool(dp[-1][-1]							)


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 # inputing the strings
 # input_string = input("input a string :")
 # pattern = input("input a pattern :")

 UpperCamelCase__ =			'aab'
 UpperCamelCase__ =			'c*a*b'

 # using function to check whether given string matches the given pattern
 if match_pattern(input_string, pattern):
  print(f"""{input_string} matches the given pattern {pattern}""")
 else:
  print(f"""{input_string} does not match with the given pattern {pattern}""")












'''simple docstring'''
def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """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 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    Dict           =     0
   lowercase_	:    Optional[Any]           =     len(_UpperCamelCase							)  # No of vertices in graph
   lowercase_	:    Union[str, Any]           =     [0] * n
   lowercase_	:    Optional[int]           =     [False] * n

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

   lowercase_	:    list[tuple[int, int]]           =     []
   for i in range(_UpperCamelCase							):
      if not visited[i]:
         dfs(_UpperCamelCase						,		-1						,		_UpperCamelCase						,		id_							)
   return bridges


if __name__ == "__main__":
 import doctest

 doctest.testmod()




