Problem Description

Depth-first search is a common search algorithm. Using this algorithm, given a simple (no multiple edges, no self-loops) undirected connected graph $G = (V, E)$ and a starting vertex $s$, we can obtain a tree $T$.

The procedure is described as follows:

1. Set the stack $S$ to be empty, and let $T = (V, \emptyset)$, i.e. the edge set of $T$ is initially empty.
2. First, push the starting vertex $s$ into $S$.
3. Visit the top vertex $u$ of the stack, and mark $u$ as “visited”.
4. If there exists a vertex adjacent to $u$ that has not been visited, then choose arbitrarily one of these vertices and denote it by $v$. Add the edge $(u, v)$ into the edge set of $T$, and push $v$ into the stack $S$, then return to Step 3. If no such vertex exists, then pop $u$ from the stack.

It can be proved that when $G$ is connected, this algorithm will produce some spanning tree $T$ of $G$. However, the tree $T$ obtained by the algorithm may not be unique: it depends on the search order, that is, the vertex chosen in Step 4. After fixing the starting vertex $s$, if there exists a specific search order such that the algorithm produces exactly $T$, then we say that $T$ is an $s$-dfs tree of $G$.

Now you are given a tree $T$ with $n$ vertices, numbered $1 \sim n$, and additionally $m$ edges are given. We guarantee that these $m$ edges are all different from each other, connect different vertices, and are all different from the $n - 1$ tree edges in $T$. We call the additional $m$ edges non-tree edges. Among these $n$ vertices, exactly $k$ vertices are specified as key vertices.

Now you want to know how many ways there are to select a subset of these $m$ non-tree edges (possibly selecting none), such that: after forming a graph $G$ using the edges of $T$ together with the selected non-tree edges, there exists some key vertex $s$ such that $T$ is an $s$-dfs tree of $G$.

Since the answer may be very large, you only need to output the number of valid selections modulo $(10 ^ 9 + 7)$.

Input Format

The first line contains an integer $c$, indicating the test point ID. $c = 0$ means this test point is the sample.

The second line contains three positive integers $n, m, k$, representing the number of vertices, the number of non-tree edges, and the number of key vertices.

The next $n - 1$ lines each contain two positive integers $u, v$, indicating an edge of the tree $T$. It is guaranteed that these $n - 1$ edges form a tree.

The next $m$ lines each contain two positive integers $a, b$, indicating a non-tree edge. It is guaranteed that $(a, b)$ does not coincide with any tree edge, and there are no multiple edges.

The last line contains $k$ positive integers $s_1, s_2, \dots, s_k$, indicating the IDs of the $k$ key vertices. It is guaranteed that $s_1, s_2, \dots, s_k$ are pairwise distinct.

Output Format

Output one line containing a non-negative integer, representing the number of valid selections modulo $(10 ^ 9 + 7)$.

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

3

见附件中的 dfs/dfs2.in。

见附件中的 dfs/dfs2.ans。

见附件中的 dfs/dfs3.in。

见附件中的 dfs/dfs3.ans。

见附件中的 dfs/dfs4.in。

见附件中的 dfs/dfs4.ans。

见附件中的 dfs/dfs5.in。

见附件中的 dfs/dfs5.ans。

见附件中的 dfs/dfs6.in。

见附件中的 dfs/dfs6.ans。

Hint

[Sample Explanation #1]

In this sample, there are three ways to select non-tree edges: select only edge $(1, 3)$, select only edge $(2, 4)$, or select no non-tree edges.

If we select only edge $(1, 3)$, or select no non-tree edges, then we can find that $T$ is a $3$-dfs tree of graph $G$. The specified search order is as follows:

1. Push $3$ into stack $S$. Now $S = [3]$.
2. Mark $3$ as “visited”.
3. Since $3$ is connected to $2$ and $2$ is “unvisited”, push $2$ into stack $S$, and add $(3, 2)$ into tree $T$. Now $S = [3, 2]$.
4. Mark $2$ as “visited”.
5. Since $2$ is connected to $1$ and $1$ is “unvisited”, push $1$ into stack $S$, and add $(2, 1)$ into tree $T$. Now $S = [3, 2, 1]$.
6. Since all vertices adjacent to $1$ are “visited”, pop $1$ from the stack. Now $S = [3, 2]$.
7. Since all vertices adjacent to $2$ are “visited”, pop $2$ from the stack. Now $S = [3]$.
8. Since $3$ is connected to $4$ and $4$ is “unvisited”, push $4$ into stack $S$, and add $(3, 4)$ into tree $T$. Now $S = [3, 4]$.
9. Since all vertices adjacent to $4$ are “visited”, pop $4$ from the stack. Now $S = [3]$.
10. Since all vertices adjacent to $3$ are “visited”, pop $3$ from the stack, and now $S$ becomes empty again.

If we select only edge $(2, 4)$, then we can show that $T$ is a $2$-dfs tree of graph $G$. The specified search order is as follows:

1. Push $2$ into stack $S$. Now $S = [2]$.
2. Mark $2$ as “visited”.
3. Since $2$ is connected to $3$ and $3$ is “unvisited”, push $3$ into stack $S$, and add $(2, 3)$ into tree $T$. Now $S = [2, 3]$.
4. Mark $3$ as “visited”.
5. Since $3$ is connected to $4$ and $4$ is “unvisited”, push $4$ into stack $S$, and add $(3, 4)$ into tree $T$. Now $S = [2, 3, 4]$.
6. Since all vertices adjacent to $4$ are “visited”, pop $4$ from the stack. Now $S = [2, 3]$.
7. Since all vertices adjacent to $3$ are “visited”, pop $3$ from the stack. Now $S = [2]$.
8. Since $2$ is connected to $1$ and $1$ is “unvisited”, push $1$ into stack $S$, and add $(2, 1)$ into tree $T$. Now $S = [2, 1]$.
9. Since all vertices adjacent to $1$ are “visited”, pop $1$ from the stack. Now $S = [2]$.
10. Since all vertices adjacent to $2$ are “visited”, pop $2$ from the stack, and now $S$ becomes empty again.

[Sample Explanation #2]

This sample satisfies the constraints of test points $4 \sim 6$.

[Sample Explanation #3]

This sample satisfies the constraints of test points $10 \sim 11$.

[Sample Explanation #4]

This sample satisfies the constraints of test points $12 \sim 13$.

[Sample Explanation #5]

This sample satisfies the constraints of test points $14 \sim 16$.

[Sample Explanation #6]

This sample satisfies the constraints of test points $23 \sim 24$.

[Constraints]

For all testdata, it is guaranteed that: $1 \le k \le n \le 5 \times 10 ^ 5$, $1 \le m \le 5 \times 10 ^ 5$.

Special property A: In $T$, vertex $i$ is connected to vertex $i + 1$ ($1 \le i < n$).

Special property B: If we form a graph $G$ using the edges of $T$ together with all $m$ non-tree edges, then $T$ is a $1$-dfs tree of $G$.

Please note that vertex $1$ is not necessarily one of the $k$ key vertices.

Translated by ChatGPT 5