




from collections import deque



def       UpperCAmelCase       (     _snake_case							):
							lowerCAmelCase   =		len(_snake_case							)
							lowerCAmelCase   =		deque()
							lowerCAmelCase   =		[False for _ in range(_snake_case							)]
							lowerCAmelCase   =		[-1 for _ in range(_snake_case							)]
							lowerCAmelCase   =		index_of[:]

							def strong_connect(_snake_case						, _snake_case						, _snake_case							):
														lowerCAmelCase   =		index  # the number when this node is seen
														lowerCAmelCase   =		index  # lowest rank node reachable from here
														index += 1
														stack.append(_snake_case							)
														lowerCAmelCase   =		True

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

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

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

							return components



def       UpperCAmelCase       (     _snake_case						, _snake_case							):
							lowerCAmelCase   =		[[] for _ in range(_snake_case							)]
							for u, v in edges:
														g[u].append(_snake_case							)
							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)









def       UpperCAmelCase       (     _snake_case						, _snake_case						, _snake_case							):

							def count_of_possible_combinations(_snake_case							) -> int:
														if target < 0:
																					return 0
														if target == 0:
																					return 1
														return sum(count_of_possible_combinations(target - item							) for item in array							)

							return count_of_possible_combinations(_snake_case							)



def       UpperCAmelCase       (     _snake_case						, _snake_case						, _snake_case							):

							def count_of_possible_combinations_with_dp_array(
							    _snake_case						, _snake_case							) -> int:
														if target < 0:
																					return 0
														if target == 0:
																					return 1
														if dp_array[target] != -1:
																					return dp_array[target]
														lowerCAmelCase   =		sum(
														    count_of_possible_combinations_with_dp_array(target - item						, _snake_case							)
														    for item in array							)
														lowerCAmelCase   =		answer
														return answer

							lowerCAmelCase   =		[-1] * (target + 1)
							return count_of_possible_combinations_with_dp_array(_snake_case						, _snake_case							)



def       UpperCAmelCase       (     _snake_case						, _snake_case						, _snake_case							):
							lowerCAmelCase   =		[0] * (target + 1)
							lowerCAmelCase   =		1

							for i in range(1						, target + 1							):
														for j in range(_snake_case							):
																					if i - array[j] >= 0:
																												dp_array[i] += dp_array[i - array[j]]

							return dp_array[target]


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		UpperCAmelCase_						=3
		UpperCAmelCase_						=5
		UpperCAmelCase_						=[1, 2, 5]
		print(combination_sum_iv(n, array, target))



