


def        UpperCamelCase_(				_A   :str				,     _A   :str  )->		bool:
			UpperCamelCase__					=       len(_A  ) + 1
			UpperCamelCase__					=       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.
			UpperCamelCase__					=       [[0 for i in range(_A  )] for j in range(_A  )]

			# since string of zero length match pattern of zero length
			UpperCamelCase__					=       1

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

			# since string of zero length will match with pattern where there
			# is at least one * alternatively
			for j in range(1				,     _A  ):
						UpperCamelCase__					=       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] == ".":
												UpperCamelCase__					=       dp[i - 1][j - 1]

									elif pattern[j - 1] == "*":
												if dp[i][j - 2] == 1:
															UpperCamelCase__					=       1
												elif pattern[j - 2] in (input_string[i - 1], "."):
															UpperCamelCase__					=       dp[i - 1][j]
												else:
															UpperCamelCase__					=       0
									else:
												UpperCamelCase__					=       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}''')






from collections import deque
def        UpperCamelCase_(				_A   :Union[str, Any]  )->		List[Any]:
			UpperCamelCase__					=       len(_A  )
			UpperCamelCase__					=       deque()
			UpperCamelCase__					=       [False for _ in range(_A  )]
			UpperCamelCase__					=       [-1 for _ in range(_A  )]
			UpperCamelCase__					=       index_of[:]

			def strong_connect(_A   :Optional[int]				,     _A   :Optional[int]				,     _A   :List[Any]  ):
						UpperCamelCase__					=       index  # the number when this node is seen
						UpperCamelCase__					=       index  # lowest rank node reachable from here
						index += 1
						stack.append(_A  )
						UpperCamelCase__					=       True

						for w in g[v]:
									if index_of[w] == -1:
												UpperCamelCase__					=       strong_connect(_A				,     _A				,     _A  )
												UpperCamelCase__					=       (
												    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
												)
									elif on_stack[w]:
												UpperCamelCase__					=       (
												    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
												)

						if lowlink_of[v] == index_of[v]:
									UpperCamelCase__					=       []
									UpperCamelCase__					=       stack.pop()
									UpperCamelCase__					=       False
									component.append(_A  )
									while w != v:
												UpperCamelCase__					=       stack.pop()
												UpperCamelCase__					=       False
												component.append(_A  )
									components.append(_A  )
						return index

			UpperCamelCase__					=       []
			for v in range(_A  ):
						if index_of[v] == -1:
									strong_connect(_A				,     0				,     _A  )

			return components
def        UpperCamelCase_(				_A   :Optional[Any]				,     _A   :Any  )->		Union[str, Any]:
			UpperCamelCase__					=       [[] for _ in range(_A  )]
			for u, v in edges:
						g[u].append(_A  )
			return g


if __name__ == "__main__":
						# Test
						__UpperCamelCase    		=       7
						__UpperCamelCase    		=       [0, 0, 1, 2, 3, 3, 4, 4, 6]
						__UpperCamelCase    		=       [1, 3, 2, 0, 1, 4, 5, 6, 5]
						__UpperCamelCase    		=       [(u, v) for u, v in zip(source, target)]
						__UpperCamelCase    		=       create_graph(n_vertices, edges)

						assert [[5], [6], [4], [3, 2, 1, 0]] == tarjan(g)


