P6651 「SWTR-5」Chain

给定 $n$ 个点，$m$ 条边的有向无环图。不保证图连通。 $q$ 次询问，每次给出 $k$ 和 $k$ 个互不相同的数 $c_i$，求出如果去掉这 $k$ 个点，整个有向无环图将剩余多少条链。答案对 $10^9+7$ 取模。**每次询问独立。** - “链”的定义是：我们设一条长度为 $p$ 的链的路径为 $w_0\to w_1\to\cdots\to w_{p-1}\to w_p$，则应满足 $w_0$ 入度为 $0$，$w_p$ 出度为 $0$。你可以将其理解为一条食物链。 - 两条链是“不同的”，当且仅当它们的长度不同，或者经过的点集不同。 - **需要特别注意的是，删去某些点后新产生的链不计入答案。** 例如 $1\to 2\to 3\to 4$ 一图中，有 $1$ 条链 $1\to 2\to 3\to 4$。如果去掉 $2$ 号点，则剩余 $0$ 条链。

第一行两个整数 $n,m$，分别表示点的个数和边的条数。 接下来 $m$ 行，每行两个整数 $u,v(u\neq v)$，表示 $u\to v$ 有一条有向边。 第 $m+2$ 行一个整数 $q$，表示询问个数。 接下来 $q$ 行： - 每行先是一个整数 $k$，表示去掉的点的个数。 - 接下来 $k$ 个整数 $c_i$，表示去掉的点的编号。

共 $q$ 行，每行表示该次询问答案对 $10^9+7$ 取模后的值。

「样例 $1$ 说明」 DAG 如图：  询问 $1$：如果去掉 $2,4,6$，则剩余 $1$ 条链：$3\to 5$。 询问 $2$：如果去掉 $4,6$，则剩余 $3$ 条链：$3\to 5$，$3\to 2\to 5$，$3\to 7\to 2\to 5$。 询问 $7$：如果去掉 $6$，则剩余 $5$ 条链：$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$。 「数据范围与约定」 **本题采用捆绑测试。** - Subtask 1（1 point）：给定的图是一条链。 - 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）：无特殊限制。 对于 $100\%$ 的数据：$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$。 所有询问满足：$1\leq \sum k\leq 2\times 10^6$，$0\leq k\leq \min(n,15)$，$1\leq c_i\leq n$。保证 $c_i$ 互不相同。 **本题轻微卡常，请注意 IO 优化。** --- 「题目来源」 [Sweet Round 05](https://www.luogu.com.cn/contest/28195) D。 idea & solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。