A7349. 古老典籍（ancient）
编程题
普及+/提高
知识点
题目描述
在浩瀚的星空之下，有一座古老的智慧神殿，殿中藏有一棵名为“真理之树”的圣物。这棵树共有 $n$ 个节点，编号为 $1 \sim n$，其中节点 $1$ 为根，每个节点都记载着一卷古老的典籍。
传说中，只有按照某种特定的从根节点 $1$ 开始的深度优先搜索（DFS）顺序阅读学习这些典籍，才能领悟其中的终极智慧。然而，守护神殿的贤者们留下了一条禁忌规则：对于给定的 $q$ 对典籍 $(a,b)$，在阅读顺序中，**节点 $a$ 的典籍必须出现在节点 $b$ 典籍之前。**
现在，你作为新一代的贤者继承者，需要计算：在遵守所有禁忌规则的前提下，一共有多少种不同的阅读顺序？
由于答案可能非常巨大，你需要输出它对 $10^9+7$ 取模的结果。
传说中，只有按照某种特定的从根节点 $1$ 开始的深度优先搜索（DFS）顺序阅读学习这些典籍，才能领悟其中的终极智慧。然而，守护神殿的贤者们留下了一条禁忌规则：对于给定的 $q$ 对典籍 $(a,b)$，在阅读顺序中，**节点 $a$ 的典籍必须出现在节点 $b$ 典籍之前。**
现在，你作为新一代的贤者继承者，需要计算：在遵守所有禁忌规则的前提下，一共有多少种不同的阅读顺序？
由于答案可能非常巨大，你需要输出它对 $10^9+7$ 取模的结果。
输入格式
输入的第一行 $t$，表示测试数据的组数。
对于每组测试数据内：
输入的第一行包含三个正整数 $n,q$，分别表示树的节点数，以及规则的数量。
接下来 $n$ 行，其中第 $i$ 行的第一个数字 $c_i$ 表示节点 $i$ 的儿子数量，接下来 $c_i$ 个数字，分别为节点 $i$ 的儿子编号。
接下来 $q$ 行，每行两个整数 $a,b$。表示典籍 $a$ 的阅读顺序必须出现在典籍 $b$ 之前。
对于每组测试数据内：
输入的第一行包含三个正整数 $n,q$，分别表示树的节点数，以及规则的数量。
接下来 $n$ 行，其中第 $i$ 行的第一个数字 $c_i$ 表示节点 $i$ 的儿子数量，接下来 $c_i$ 个数字，分别为节点 $i$ 的儿子编号。
接下来 $q$ 行，每行两个整数 $a,b$。表示典籍 $a$ 的阅读顺序必须出现在典籍 $b$ 之前。
输出格式
输出 $t$ 行，每行一个数字，表示符合规则的阅读顺序方案数，对 $10^9+7$ 取模。
输入输出样例
输入 #1
2 6 1 3 2 3 4 2 5 6 0 0 0 0 2 3 6 2 3 2 3 4 2 5 6 0 0 0 0 2 3 3 5
输出 #1
6 0
说明/提示
### 样例 1 解释
样例包含两组测试数据，两组测试数据的树都如下图：
其中第一组测试数据要求节点 $2$ 的典籍必须出现在典籍 $3$ 之前。有 $6$ 种满足条件的 DFS 顺序：
```text
1,2,5,6,3,4
1,2,6,5,3,4
1,2,5,6,4,3
1,2,6,5,4,3
1,4,2,5,6,3
1,4,2,6,5,3
```
其中第二组测试数据相比第一组测试数据增加一条限制，为节点 $3$ 的典籍必须出现在典籍 $5$ 之前。上面 $6$ 种 DFS 顺序均不能使得 $3$ 在 $5$ 之前，满足条件的 DFS 顺序数为 $0$。
### 附件
更多样例请查看：[ancient test.zip](https://pms-wscdn.xmwol.com/file/1bf8ce5fe2d35f9e.zip)
### 数据范围
对于所有测试数据有：
$$ 1 \le t \le 5 $$
$$ 1 \le n \le 5 \times 10^4 $$
$$ 0 \le q \le 5 \times 10^4 $$
$$ 0 \le c_i \le 15 $$
$$ a \ne b $$
| 测试点 | $n \le$ | $q \le$ | $c_i \le$ | 特殊性质 |
| ----- | --------------- | --------------- | --------- | --------------------- |
| 1~3 | 10 | 10 | 10 | |
| 4~5 | 10 | 10 | 10 | $c_1=n-1$ |
| 6~7 | 30 | 30 | 10 | |
| 8~9 | $10^2$ | 2 | 2 | |
| 10~11 | $10^2$ | $10^2$ | 10 | |
| 12~13 | $10^3$ | 0 | 10 | |
| 14 | $10^3$ | 1 | 10 | |
| 15~17 | $10^3$ | $10^3$ | 10 | |
| 18 | $10^4$ | $10^4$ | 10 | 所有规则的 $a,b$ 其中一个为 $1$ |
| 19 | $10^4$ | 3 | 10 | |
| 20 | $10^4$ | $10^4$ | 2 | |
| 21~25 | $5 \times 10^4$ | $5 \times 10^4$ | 15 | |
样例包含两组测试数据，两组测试数据的树都如下图：
其中第一组测试数据要求节点 $2$ 的典籍必须出现在典籍 $3$ 之前。有 $6$ 种满足条件的 DFS 顺序：
```text
1,2,5,6,3,4
1,2,6,5,3,4
1,2,5,6,4,3
1,2,6,5,4,3
1,4,2,5,6,3
1,4,2,6,5,3
```
其中第二组测试数据相比第一组测试数据增加一条限制，为节点 $3$ 的典籍必须出现在典籍 $5$ 之前。上面 $6$ 种 DFS 顺序均不能使得 $3$ 在 $5$ 之前，满足条件的 DFS 顺序数为 $0$。
### 附件
更多样例请查看：[ancient test.zip](https://pms-wscdn.xmwol.com/file/1bf8ce5fe2d35f9e.zip)
### 数据范围
对于所有测试数据有：
$$ 1 \le t \le 5 $$
$$ 1 \le n \le 5 \times 10^4 $$
$$ 0 \le q \le 5 \times 10^4 $$
$$ 0 \le c_i \le 15 $$
$$ a \ne b $$
| 测试点 | $n \le$ | $q \le$ | $c_i \le$ | 特殊性质 |
| ----- | --------------- | --------------- | --------- | --------------------- |
| 1~3 | 10 | 10 | 10 | |
| 4~5 | 10 | 10 | 10 | $c_1=n-1$ |
| 6~7 | 30 | 30 | 10 | |
| 8~9 | $10^2$ | 2 | 2 | |
| 10~11 | $10^2$ | $10^2$ | 10 | |
| 12~13 | $10^3$ | 0 | 10 | |
| 14 | $10^3$ | 1 | 10 | |
| 15~17 | $10^3$ | $10^3$ | 10 | |
| 18 | $10^4$ | $10^4$ | 10 | 所有规则的 $a,b$ 其中一个为 $1$ |
| 19 | $10^4$ | 3 | 10 | |
| 20 | $10^4$ | $10^4$ | 2 | |
| 21~25 | $5 \times 10^4$ | $5 \times 10^4$ | 15 | |