Implement a Dependency-Aware Todo List with Cascade Failure

Problem: Implement a Dependency-Aware Todo List with Cascade Failure Implement a Todo management module in Python. Each task may depend on other tasks, and may also be depended on by other tasks. You must maintain two relations: dependencies: the set of task IDs that the current task depends on (if A depends on B, then B is in A.dependencies) dependents: the set of task IDs that depend on the current task (if A depends on B, then A is in B.dependents) You must support cascade failure: when a task is marked as failed, every task that directly or indirectly depends on it must also be marked as failed. Data Model Each task has: task_id: unique identifier status: at least PENDING, DONE, FAILED dependencies: set of dependency task IDs dependents: set of dependent task IDs Required API Implement a TodoList class with at least: add_task(task_id: str) -> None Add a new task, initial status PENDING. If the task already exists, either keep it idempotent or raise an error (choose one consistent behavior). add_dependency(task_id: str, dependency_id: str) -> None Declare that task_id depends on dependency_id. Update both sides: add dependency_id to task_id.dependencies add task_id to dependency_id.dependents If tasks do not exist, define a consistent behavior (auto-create or raise). mark_failed(task_id: str) -> None Mark task_id as FAILED. Trigger cascade failure: all tasks that directly or indirectly depend on task_id must become FAILED. Must: avoid re-processing the same task (no infinite loops) terminate even if the dependency graph contains cycles get_status(task_id: str) -> str Return the current status. Constraints Number of tasks can be in the hundreds to thousands. Dependencies form a directed graph and may contain cycles. mark_failed must be efficient on large graphs (avoid timeouts). Examples Tasks: A, B, C Dependencies: A depends on B, C depends on A After mark_failed(B): B fails A depends on B → fails C depends on A (indirectly on B) → fails Sample Test Cases (5) Single task fails Input: add A; mark_failed(A) Output: A=FAILED One-level cascade Input: A depends on B; mark_failed(B) Output: A=FAILED, B=FAILED Multi-level cascade Input: C depends on A; A depends on B; mark_failed(B) Output: A=FAILED, B=FAILED, C=FAILED Diamond dependencies Input: D depends on B and C; B depends on A; C depends on A; mark_failed(A) Output: A=FAILED, B=FAILED, C=FAILED, D=FAILED Cycle must terminate Input: A depends on B; B depends on A; mark_failed(A) Output: A=FAILED, B=FAILED Example Input add_task A mark_failed A get_status A Output FAILED