Problem Description

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.

Input Format

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 Format

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

7 14
3 2
4 5
2 5
2 6
3 1
3 5
3 7
3 6
6 4
1 4
6 5
1 6
7 2
7 4
7
3 2 4 6
2 4 6
2 2 5
2 1 4
0
1 4
1 6

1
3
0
6
13
7
5

233 1
1 2
6
0
1 10
2 10 40
1 1
1 2
2 1 2

232
231
230
231
231
231

Hint

"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 D.
Idea & solution: Alex_Wei.

Translated by ChatGPT 5