9585 - 深搜

通过次数

1

提交次数

22

时间限制 : 6 秒
内存限制 : 512 MB

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

算法的流程描述如下:

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

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

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

现在你想知道,有多少种选取这 m 条非树边的方法(可以全部不选),使得:将 T 的边与被选中的非树边构成图 G 之后,存在某个关键点 s,使得 TG 的一棵 s-dfs 树。

由于答案可能十分巨大,你只需要输出方案数在模 (10 ^ 9 + 7) 意义下的值。

输入

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

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

接下来 n - 1 行,每行包含两个正整数 u, v 表示树 T 的一条边。保证这 n - 1 条边构成了一棵树。

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

输入的最后一行包含 k 个正整数 s_1, s_2, \dots, s_k,表示 k 个关键点的编号。保证 s_1, s_2, \dots, s_k 互不相同。

输出

输出一行包含一个非负整数,表示方案数在模 (10 ^ 9 + 7) 意义下的值。

样例

输入

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

输出

3

提示

【样例解释 #1】

在这个样例中,有三种选取非树边的方法:只选取边 (1, 3),只选取边 (2, 4),或不选取任何条非树边。

如果只选取边 (1, 3),或者不选取任何一条非树边,则我们发现 T 都是图 G3-dfs 树。指定的搜索顺序如下:

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

如果只选取边 (2, 4),则我们可以说明 T 是图 G2-dfs 树。指定的搜索顺序如下:

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

对于所有测试数据保证:1 \le k \le n \le 5 \times 10 ^ 51 \le m \le 5 \times 10 ^ 5

测试点编号n \lem \lek \le特殊性质
1 \sim 366n
4 \sim 615156
7 \sim 93003006
10 \sim 11300300nA
12 \sim 13300300nB
14 \sim 16300300n
17 \sim 182 \times 10 ^ 52 \times 10 ^ 5nA
19 \sim 212 \times 10 ^ 52 \times 10 ^ 5nB
222 \times 10 ^ 52 \times 10 ^ 5n
23 \sim 255 \times 10 ^ 55 \times 10 ^ 5n

特殊性质 A:保证在 T 中,i 号点与 i + 1 号点相连(1 \le i < n)。

特殊性质 B:保证若将 T 的边与所有 m 条非树边构成一个图 G,则 TG 的棵 1-dfs 树。

请注意,1 号点不一定是 k 个关键点之一。

来源

NOI