P6651 "SWTR-5" Chain

You are given a directed acyclic graph (DAG) with $n$ vertices and $m$ edges. The graph is not guaranteed to be connected. There are $q$ queries. In each query, you are given $k$ and $k$ pairwise distinct numbers $c_i$. You need to compute: if these $k$ vertices are removed, how many chains will remain in the whole DAG. The answer should be taken modulo $10^9+7$. **Each query is independent.** - Definition of a “chain”: Suppose a chain of length $p$ has the path $w_0\to w_1\to\cdots\to w_{p-1}\to w_p$. It should satisfy that $w_0$ has indegree $0$ and $w_p$ has outdegree $0$. You can think of it as a food chain. - Two chains are “different” if and only if they have different lengths, or the sets of vertices they pass through are different. - **Note carefully that chains newly created after deleting some vertices are not counted in the answer.** For example, in the graph $1\to 2\to 3\to 4$, there is $1$ chain $1\to 2\to 3\to 4$. If vertex $2$ is removed, then $0$ chains remain.

The first line contains two integers $n,m$, representing the number of vertices and the number of edges. The next $m$ lines each contain two integers $u,v(u\neq v)$, meaning there is a directed edge $u\to v$. Line $m+2$ contains an integer $q$, representing the number of queries. The next $q$ lines: - Each line first contains an integer $k$, representing the number of vertices to remove. - Then follow $k$ integers $c_i$, representing the indices of the vertices to remove.

Output $q$ lines. Each line is the answer for that query modulo $10^9+7$.

"Sample 1 Explanation" The DAG is shown in the figure:  Query $1$: If $2,4,6$ are removed, then $1$ chain remains: $3\to 5$. Query $2$: If $4,6$ are removed, then $3$ chains remain: $3\to 5$, $3\to 2\to 5$, $3\to 7\to 2\to 5$. Query $7$: If $6$ is removed, then $5$ chains remain: $3\to 5$, $3\to 2\to 5$, $3\to 7\to 2\to 5$, $3\to 1\to 4\to 5$, $3\to 7\to 4\to 5$. "Constraints and Notes" **This problem uses bundled testdata.** - Subtask 1 (1 point): The given graph is a single chain. - Subtask 2 (14 points): $n,q\leq 10$. - Subtask 3 (20 points): $q\leq 10^3$. - Subtask 4 (17 points): $k=1$. - Subtask 5 (18 points): $k=2$. - Subtask 6 (30 points): No special restrictions. For $100\%$ of the testdata: $2\leq n\leq 2\times 10^3$, $1\leq m\leq \min(\frac{n\times(n-1)}{2},2\times 10^4)$, $1\leq q\leq 5\times 10^5$. All queries satisfy: $1\leq \sum k\leq 2\times 10^6$, $0\leq k\leq \min(n,15)$, $1\leq c_i\leq n$. It is guaranteed that all $c_i$ are pairwise distinct. **This problem is slightly time-tight, so please pay attention to IO optimization.** --- "Source" [Sweet Round 05](https://www.luogu.com.cn/contest/28195) D. Idea & solution: [Alex_Wei](https://www.luogu.com.cn/user/123294). Translated by ChatGPT 5