
'''simple docstring'''






class     __snake_case		:
					def __init__(     self      ):

									"""simple docstring"""


									lowerCamelCase					:			Any									= """"""
									lowerCamelCase					:			List[str]									= """"""
									lowerCamelCase					:			List[Any]									= []
					def     UpperCAmelCase_							(     self,    A,    A      ):

									"""simple docstring"""


									if m == -1:
													return n + 1
									elif n == -1:
													return m + 1
									elif self.dp[m][n] > -1:
													return self.dp[m][n]
									else:
													if self.worda[m] == self.worda[n]:
																	lowerCamelCase					:			int									= self.__min_dist_top_down_dp(m - 1,    n - 1      )
													else:
																	lowerCamelCase					:			Tuple									= self.__min_dist_top_down_dp(A,    n - 1      )
																	lowerCamelCase					:			str									= self.__min_dist_top_down_dp(m - 1,    A      )
																	lowerCamelCase					:			List[Any]									= self.__min_dist_top_down_dp(m - 1,    n - 1      )
																	lowerCamelCase					:			Optional[int]									= 1 + min(A,    A,    A      )

													return self.dp[m][n]
					def     UpperCAmelCase_							(     self,    A,    A      ):

									"""simple docstring"""


									lowerCamelCase					:			List[Any]									= worda
									lowerCamelCase					:			int									= worda
									lowerCamelCase					:			str									= [[-1 for _ in range(len(A      )      )] for _ in range(len(A      )      )]

									return self.__min_dist_top_down_dp(len(A      ) - 1,    len(A      ) - 1      )




					def     UpperCAmelCase_							(     self,    A,    A      ):

									"""simple docstring"""


									lowerCamelCase					:			str									= worda
									lowerCamelCase					:			Any									= worda
									lowerCamelCase					:			str									= len(A      )
									lowerCamelCase					:			Tuple									= len(A      )
									lowerCamelCase					:			Union[str, Any]									= [[0 for _ in range(n + 1      )] for _ in range(m + 1      )]

									for i in range(m + 1      ):
													for j in range(n + 1      ):
																	if i == 0:  # first string is empty
																					lowerCamelCase					:			List[Any]									= j
																	elif j == 0:  # second string is empty
																					lowerCamelCase					:			List[Any]									= i
																	elif worda[i - 1] == worda[j - 1]:  # last characters are equal
																					lowerCamelCase					:			List[Any]									= self.dp[i - 1][j - 1]
																	else:
																					lowerCamelCase					:			int									= self.dp[i][j - 1]
																					lowerCamelCase					:			List[Any]									= self.dp[i - 1][j]
																					lowerCamelCase					:			Union[str, Any]									= self.dp[i - 1][j - 1]
																					lowerCamelCase					:			List[Any]									= 1 + min(A,    A,    A      )
									return self.dp[m][n]


if __name__ == "__main__":
					A			      =      EditDistance()

					print('****************** Testing Edit Distance DP Algorithm ******************')
					print()

					A			      =      input('Enter the first string: ').strip()
					A			      =      input('Enter the second string: ').strip()

					print()
					print(f"""The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}""")
					print(f"""The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}""")
					print()
					print('*************** End of Testing Edit Distance DP Algorithm ***************')


'''simple docstring'''






A			      =      {'a': ['c', 'b'], 'b': ['d', 'e'], 'c': [], 'd': [], 'e': []}
A			      =      ['a', 'b', 'c', 'd', 'e']





def    UpperCAmelCase							(  UpperCAmelCase__							:							Union[str, Any]       ,							UpperCAmelCase__							:							Any       ,							UpperCAmelCase__							:							List[Any]):
				lowerCamelCase					:			List[Any]									= start
				# add current to visited
				visited.append(UpperCAmelCase__)
				lowerCamelCase					:			List[str]									= edges[current]
				for neighbor in neighbors:
								# if neighbor not in visited, visit
								if neighbor not in visited:
												lowerCamelCase					:			Any									= topological_sort(UpperCAmelCase__       ,							UpperCAmelCase__       ,							UpperCAmelCase__)
    # if all neighbors visited add current to sort
				sort.append(UpperCAmelCase__)
				# if all vertices haven't been visited select a new one to visit
				if len(UpperCAmelCase__) != len(UpperCAmelCase__):
								for vertice in vertices:
												if vertice not in visited:
																lowerCamelCase					:			List[str]									= topological_sort(UpperCAmelCase__       ,							UpperCAmelCase__       ,							UpperCAmelCase__)
    # return sort
				return sort


if __name__ == "__main__":
					A			      =      topological_sort('a', [], [])
					print(sort)
