P9480 [NOI2023] DFS

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)$.

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 one line containing a non-negative integer, representing the number of valid selections modulo $(10 ^ 9 + 7)$.

**[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$. |Test Point ID|$n \le$|$m \le$|$k \le$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$1 \sim 3$|$6$|$6$|$n$|None| |$4 \sim 6$|$15$|$15$|$6$|None| |$7 \sim 9$|$300$|$300$|$6$|None| |$10 \sim 11$|$300$|$300$|$n$|A| |$12 \sim 13$|$300$|$300$|$n$|B| |$14 \sim 16$|$300$|$300$|$n$|None| |$17 \sim 18$|$2 \times 10 ^ 5$|$2 \times 10 ^ 5$|$n$|A| |$19 \sim 21$|$2 \times 10 ^ 5$|$2 \times 10 ^ 5$|$n$|B| |$22$|$2 \times 10 ^ 5$|$2 \times 10 ^ 5$|$n$|None| |$23 \sim 25$|$5 \times 10 ^ 5$|$5 \times 10 ^ 5$|$n$|None| 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