

def 					lowerCAmelCase__							(	SCREAMING_SNAKE_CASE_:							List[str]      )			->      Dict:




				'''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 					lowerCAmelCase__							(	SCREAMING_SNAKE_CASE_:							dict[int, list[int]]      )			->      list[tuple[int, int]]:




				'''simple docstring'''





				A__        =			0
				A__        =			len(SCREAMING_SNAKE_CASE_      )  # No of vertices in graph
				A__        =			[0] * n
				A__        =			[False] * n

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

				A__        =			[]
				for i in range(SCREAMING_SNAKE_CASE_      ):
								if not visited[i]:
												dfs(SCREAMING_SNAKE_CASE_	,       -1	,       SCREAMING_SNAKE_CASE_	,       id_      )
				return bridges


if __name__ == "__main__":
	import doctest

	doctest.testmod()




from __future__ import annotations



def 					lowerCAmelCase__							(	SCREAMING_SNAKE_CASE_:							str	,       SCREAMING_SNAKE_CASE_:							list[str] | None = None      )			->      list[list[str]]:




				'''simple docstring'''





				A__        =			word_bank or []
				# create a table
				A__        =			len(SCREAMING_SNAKE_CASE_      ) + 1

				A__        =			[]
				for _ in range(SCREAMING_SNAKE_CASE_      ):
								table.append([]      )
				# seed value
				A__        =			[[]]  # because empty string has empty combination

				# iterate through the indices
				for i in range(SCREAMING_SNAKE_CASE_      ):
								# condition
								if table[i] != []:
												for word in word_bank:
																# slice condition
																if target[i : i + len(SCREAMING_SNAKE_CASE_      )] == word:
																				A__        =			[
																				    [word, *way] for way in table[i]
																				]
																				# adds the word to every combination the current position holds
																				# now,push that combination to the table[i+len(word)]
																				table[i + len(SCREAMING_SNAKE_CASE_      )] += new_combinations

    # combinations are in reverse order so reverse for better output
				for combination in table[len(SCREAMING_SNAKE_CASE_      )]:
								combination.reverse()

				return table[len(SCREAMING_SNAKE_CASE_      )]


if __name__ == "__main__":
	print(all_construct("""jwajalapa""", ["""jwa""", """j""", """w""", """a""", """la""", """lapa"""]))
	print(all_construct("""rajamati""", ["""s""", """raj""", """amat""", """raja""", """ma""", """i""", """t"""]))
	print(
	    all_construct(
	        """hexagonosaurus""",
	        ["""h""", """ex""", """hex""", """ag""", """ago""", """ru""", """auru""", """rus""", """go""", """no""", """o""", """s"""],
	    )
	)

