A7349 | $古老典籍（ancient）$

时间限制3s

内存限制1024MB

通过 / 提交0/0

题目描述

在浩瀚的星空之下，有一座古老的智慧神殿，殿中藏有一棵名为“真理之树”的圣物。这棵树共有 $n$ 个节点，编号为 $1 \sim n$，其中节点 $1$ 为根，每个节点都记载着一卷古老的典籍。 传说中，只有按照某种特定的从根节点 $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$ 之前。

输出 $t$ 行，每行一个数字，表示符合规则的阅读顺序方案数，对 $10^9+7$ 取模。

输入 #1

输出 #1

6
0

### 样例 1 解释 样例包含两组测试数据，两组测试数据的树都如下图： ![](/uploads/acgo/image/aad5a18c2587c8f4_60e8d3d0898f.png) 其中第一组测试数据要求节点 $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 | |

C++ 编辑器

输入

输出