7305 - 古老典籍（ancient）

在浩瀚的星空之下，有一座古老的智慧神殿，殿中藏有一棵名为“真理之树”的圣物。这棵树共有n个节点，编号为1~n,其中节点1为根，每个节点都记载着一卷古老的典籍。

传说中，只有按照某种特定的从根节点1开始的深度优先搜索（DFS）顺序阅读学习这些典籍，才能领悟其中的终极智慧。然而，守护神殿的贤者们留下了一条禁忌规则：对于给定的q对典籍(a,b)，在阅读顺序中，节点\mathbit{a}的典籍必须出现在节点\mathbit{b}典籍之前。

现在，你作为新一代的贤者继承者，需要计算：在遵守所有禁忌规则的前提下，一共有多少种不同的阅读顺序？

由于答案可能非常巨大，你需要输出它对{10}^9+7取模的结果。

从文件ancient.in中读入数据。本题包含多组测试数据。

输入的第一行t，表示测试数据的组数。

对于每组测试数据内：

输入的第一行包含三个正整数 n,q，分别表示树的节点数，以及规则的数量。

接下来n行，其中第i行的第一个数字c_i表示节点i的儿子数量，接下来c_i个数字，分别为节点i的儿子编号。

接下来q行，每行两个整数a,b。表示典籍a的阅读顺序必须出现在典籍b之前。

输出到文件ancient.out中。

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

样例包含两组测试数据，两组测试数据的树都如下图：

其中第一组测试数据要求节点2的典籍必须出现在典籍3之前。有6种满足条件的DFS顺序：

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。

青少年编程挑战赛