



"""simple docstring"""







def 				UpperCamelCase_    (    lowerCAmelCase__      :				str    ,   lowerCAmelCase__      :				str						)						->   bool:

  """simple docstring"""




  lowerCAmelCase_   :				Tuple								= len(lowerCAmelCase__						) + 1
  lowerCAmelCase_   :				List[Any]								= len(lowerCAmelCase__						) + 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.
  lowerCAmelCase_   :				Optional[Any]								= [[0 for i in range(lowerCAmelCase__						)] for j in range(lowerCAmelCase__						)]

  # since string of zero length match pattern of zero length
  lowerCAmelCase_   :				List[str]								= 1

  # since pattern of zero length will never match with string of non-zero length
  for i in range(1    ,   lowerCAmelCase__						):
    lowerCAmelCase_   :				Optional[int]								= 0

  # since string of zero length will match with pattern where there
  # is at least one * alternatively
  for j in range(1    ,   lowerCAmelCase__						):
    lowerCAmelCase_   :				Union[str, Any]								= 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    ,   lowerCAmelCase__						):
    for j in range(1    ,   lowerCAmelCase__						):
      if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
        lowerCAmelCase_   :				Dict								= dp[i - 1][j - 1]

      elif pattern[j - 1] == "*":
        if dp[i][j - 2] == 1:
          lowerCAmelCase_   :				str								= 1
        elif pattern[j - 2] in (input_string[i - 1], "."):
          lowerCAmelCase_   :				Tuple								= dp[i - 1][j]
        else:
          lowerCAmelCase_   :				Dict								= 0
      else:
        lowerCAmelCase_   :				Union[str, Any]								= 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 :")

     lowercase__		:				Optional[int]          =	"""aab"""
     lowercase__		:				Tuple          =	"""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 				UpperCamelCase_    (    lowerCAmelCase__      :				Optional[Any]						)						->   Optional[int]:

  """simple docstring"""




  lowerCAmelCase_   :				Tuple								= [0] * len(lowerCAmelCase__						)
  lowerCAmelCase_   :				List[str]								= []
  lowerCAmelCase_   :				Tuple								= [1] * len(lowerCAmelCase__						)

  for values in graph.values():
    for i in values:
      indegree[i] += 1

  for i in range(len(lowerCAmelCase__						)						):
    if indegree[i] == 0:
      queue.append(lowerCAmelCase__						)

  while queue:
    lowerCAmelCase_   :				Union[str, Any]								= queue.pop(0						)
    for x in graph[vertex]:
      indegree[x] -= 1

      if long_dist[vertex] + 1 > long_dist[x]:
        lowerCAmelCase_   :				Any								= long_dist[vertex] + 1

      if indegree[x] == 0:
        queue.append(lowerCAmelCase__						)

  print(max(lowerCAmelCase__						)						)


# Adjacency list of Graph
lowercase__		:				Any          =	{0: [2, 3, 4], 1: [2, 7], 2: [5], 3: [5, 7], 4: [7], 5: [6], 6: [7], 7: []}
longest_distance(graph)





