#2026. 「NOI 2023」深搜

深度优先搜索是一种常见的搜索算法。通过此算法，我们可以从一个无重边、无自环的无向连通图 ，和某个出发点 ，得到一棵树 。

算法的流程描述如下:

1. 将栈 设置为空，并令 ，即 的边集初始为空。
2. 首先将出发点 压入 中。
3. 访问栈顶节点 ，并将 标记为“已访问的”。
4. 如果存在与 相邻且未被访问的节点，则任意地从这些节点中挑选一个记为 。我们将边 加入 的边集中，并将 压入栈 中，然后回到步骤 3。若不存在这样的节点，则从栈中弹出节点 。

可以证明，当图 为连通图时，该算法会得到图的某一棵生成树 。但算法得到的树 可能不是唯一的，它取决于搜索的顺序，也就是算法的第 4 步所选取的顶点。指定出发点 后，如果能够选取一种特定的搜索顺序，使得算法得到的树恰好是 ，则我们称 是 的一棵 -dfs 树。

现在给定一棵 个顶点的树 ，顶点编号为 ，并额外给出 条边。我们保证这 条边两两不同，连接不同的顶点，且与 中的 条树边两两不同。我们称额外给出的 条边为非树边。在这 个顶点中，我们指定了恰好 个顶点作为关键点。

现在你想知道，有多少种选取这 条非树边的方法（可以全部不选），使得：将 的边与被选中的非树边构成图 之后，存在某个关键点 ，使得 是 的一棵 -dfs 树。

由于答案可能十分巨大，你只需要输出方案数在模 意义下的值。

从文件 dfs.in 中读取数据。

输入的第一行包含一个整数 ，表示测试点编号。 表示该测试点为样例。

输入的第二行包含三个正整数 ，分别表示顶点个数，非树边的数量，关键点的数量。

接下来 行，每行包含两个正整数 表示树 的一条边。保证这 条边构成了一棵树。

接下来 行，每行包含两个正整数 表示一条非树边。保证 不与树上的边重合，且没有重边。

输入的最后一行包含 个正整数 ，表示 个关键点的编号。保证 互不相同。

输出到文件 dfs.out 中。

输出一行包含一个非负整数，表示方案数在模 意义下的值。

样例 1 输入

0
4 2 2
1 2
2 3
3 4
1 3
2 4
2 3

样例 1 输出

3

样例 1 解释

在这个样例中，有三种选取非树边的方法：只选取边 ，只选取边 ，或不选取任何条非树边。

如果只选取边 ，或者不选取任何一条非树边，则我们发现 都是图 的 -dfs 树。指定的搜索顺序如下：

1. 将 放入栈 中。此时 。
2. 将 标记为“已访问的”。
3. 由于 与 相连，且 是“未访问的”，将 放入栈 中，并将 加入树 中，此时 。
4. 将 标记为“已访问的”。
5. 由于 与 相连，且 是“未访问的”，将 放入栈 中，并将 加入树 中，此时 。
6. 由于与 相邻的点都是“已访问的”，将 弹出栈，此时 。
7. 由于与 相邻的点都是“已访问的”，将 弹出栈，此时 。
8. 由于 与 相连，且 是“未访问的”，将 放入栈 中，并将 加入树 中，此时 。
9. 由于与 相连的点都是“已访问的”，将 弹出栈，此时 。
10. 由于与 相连的点都是“己访问的”，将 弹出栈，此时 重新变为空。

如果只选取边 ，则我们可以说明 是图 的 -dfs 树。指定的搜索顺序如下：

1. 将 放入栈 中。此时 。
2. 将 标记为“已访问的”。
3. 由于 与 相连，且 是“未访问的”，将 放入栈 中，并将 加入树 中，此时 。
4. 将 标记为“已访问的”。
5. 由于 与 相连，且 是“未访问的”，将 放入栈 中，并将 加入树 中，此时 。
6. 由于与 相邻的点都是“己访问的”，将 弹出栈，此时 。
7. 由于与 相邻的点都是“已访问的”，将 弹出栈，此时 。
8. 由于 与 相连，且 是“未访问的”，将 放入栈 中，并将 加入树 中，此时 。
9. 由于与 相连的点都是“已访问的”，将 弹出栈此时 。
10. 由于与 相连的点都是“已访问的”，将 弹出栈，此时 重新变为空。

样例 2

见附件中的 dfs/dfs2.in 与 dfs/dfs2.ans。

这个样例满足测试点 的约束条件。

样例 3

见附件中的 dfs/dfs3.in 与 dfs/dfs3.ans。

这个样例满足测试点 的约束条件。

样例 4

见附件中的 dfs/dfs4.in 与 dfs/dfs4.ans。

这个样例满足测试点 的约束条件。

样例 5

见附件中的 dfs/dfs5.in 与 dfs/dfs5.ans。

这个样例满足测试点 的约束条件。

样例 6

见附件中的 dfs/dfs6.in 与 dfs/dfs6.ans。

这个样例满足测试点 的约束条件。

对于所有测试数据保证：，。

特殊性质 A：保证在 中， 号点与 号点相连（）。

特殊性质 B：保证若将 的边与所有 条非树边构成一个图 ，则 是 的棵 -dfs 树。

请注意， 号点不一定是 个关键点之一。