def dfs(caves: dict[(str, list[str])], current: str, visited: (set[str] | None)=None) -> int:
    if (current == 'end'):
        return 1
    nb_paths = 0
    if (visited is None):
        visited = set()
    for cave in caves[current]:
        if (cave in visited):
            continue
        nb_paths += dfs(caves, cave, ((visited | {current}) if current.islower() else visited))
    return nb_paths
def dfs(caves: dict[(str, list[str])], current: str, visited: (set[str] | None)=None) -> int:
    if (current == 'end'):
        return 1
    nb_paths = 0
    if (visited is None):
        visited = set()
    for cave in caves[current]:
        if (cave in visited):
            continue
        nb_paths += dfs(caves, cave, ((visited | {current}) if current.islower() else visited))
    return nb_paths