시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 1024 MB0000.000%

문제

Depth-first search is a common search algorithm. Using this algorithm, we can obtain a tree $T$ from an undirected connected graph $G = (V,E)$ with no self-loops nor parallel edges, and a certain starting point $s$.

The algorithm can be described as follows:

  • Set the stack $S$ to be empty, and let $T = (V, \emptyset)$, which means that the edge set of $T$ is initially empty.
  • First, push the starting point $s$ into $S$.
  • Visit the top vertex $u$ of the stack and mark u as "visited".
  • If there is a vertex $v$ adjacent to u and not yet visited, arbitrarily select one from these vertices and let $(u, v)$ be added to the edge set of $T$. Then, push $v$ into the stack $S$, and go back to step $3$. If there is no such vertex, pop $u$ out of the stack.

It can be proved that when $G$ is a connected graph, the algorithm will obtain a certain spanning tree $T$ of $G$. However, the tree $T$ obtained by the algorithm may not be unique, depending on the search order, i.e., the vertex selected in step 4. If a specific search order can be chosen so that the tree obtained by the algorithm is exactly $T$, then we call $T$ an $s$-dfs tree of $G$ with respect to the starting point $s$.

Now, given a tree $T$ with $n$ vertices labeled from $1$ to $n$, and an additional $m$ edges, we guarantee that these $m$ edges are distinct and connect different vertices, and are different from the $n-1$ tree edges in $T$. We call these additional $m$ edges non-tree edges. Among these $n$ vertices, we specify exactly $k$ vertices as special vertices.

Now, you want to know how many ways there are to select a subset of these $m$ non-tree edges (you can possibly select none) such that: after the tree edges of $T$ and the selected non-tree edges are combined to form a graph $G$, there exists a special 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 solutions modulo $(10^9+7)$.

입력

The first line of input contains an integer $c$, which represents the test case number. $c = 0$ represents that this test case is a sample test.

The second line of input contains three positive integers $n, m, k$, which represent the number of vertices, the number of non-tree edges, and the number of critical points, respectively.

Then $n-1$ lines follow, each containing two positive integers $u, v$, representing a tree edge of $T$. It is guaranteed that these $n-1$ edges form a tree.

Then $m$ lines follow, each containing two positive integers $a, b$, representing a non-tree edge. It is guaranteed that $(a, b)$ does not coincide with an edge on the tree and there are no duplicate edges.

The last line of input contains $k$ positive integers $s_1, s_2, ..., s_k$, representing the labels of the $k$ special vertices. It is guaranteed that $s_1, s_2, ..., s_k$ are distinct from each other.

출력

Output a line containing an integer, representing the number of solutions, taken modulo $(10^9+7)$.

제한

For all test data, it is guaranteed that: $1 \leq k \leq n \leq 5\cdot 10^5,1\leq m\leq 5\cdot 10^5$.

예제 입력 1

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

예제 출력 1

3

In this sample, there are three ways to select the non-tree edges: selecting only the edge $(1, 3)$, selecting only the edge $(2, 4)$, or not selecting any non-tree edges. If we select only the edge $(1, 3)$, or do not select any non-tree edges, we can show that $T$ is a $3$-dfs tree of $G$. The specified search order is as follows:

  • Put $3$ into the stack $S$. At this time, $S = [3]$.
  • Mark $3$ as "visited".
  • Since $3$ is adjacent to $2$ and $2$ is "unvisited", put $2$ into the stack $S$ and add $(3,2)$ to tree $T$. At this time, $S = [3, 2]$.
  • Mark $2$ as "visited".
  • Since $2$ is adjacent to $1$ and $1$ is "unvisited", put $1$ into stack $S$ and add $(2,1)$ to tree $T$. At this time, $S = [3, 2, 1]$.
  • Since all the vertices adjacent to $1$ are "visited", pop $1$ off the stack. At this time, $S = [3, 2]$.
  • Since all the vertices adjacent to $2$ are "visited", pop $2$ off the stack. At this time, $S = [3]$.
  • Since $3$ is adjacent to $4$ and $4$ is "unvisited", put $4$ into stack $S$ and add $(3,4)$ to tree T. At this time, $S = [3, 4]$.
  • Since all the vertices adjacent to $4$ are "visited", pop $4$ off the stack. At this time, $S = [3]$.
  • Since all the vertices adjacent to $3$ are "visited", pop $3$ off the stack and $S$ becomes empty again.

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

  • Put $2$ into stack $S$. At this time, $S = [2]$.
  • Mark $2$ as "visited".
  • Since $2$ is adjacent to $3$ and $3$ is "unvisited", put $3$ into the stack $S$, and add $(2,3)$ to tree $T$. At this time, $S = [2,3]$.
  • Mark $3$ as "visited".
  • Since $3$ is adjacent to $4$ and $4$ is "unvisited", put $4$ into the stack $S$, and add $(3,4)$ to tree $T$. At this time, $S = [2,3,4]$.
  • Since all the neighboring vertices of $4$ are "visited", pop $4$ out of the stack. At this time, $S = [2,3]$.
  • Since all the neighboring vertices of $3$ are "visited", pop $3$ out of the stack. At this time, $S = [2]$.
  • Since $2$ is adjacent to $1$ and $1$ is "unvisited", put $1$ into the stack $S$, and add $(2,1)$ to tree T. At this time, $S = [2,1]$.
  • Since all the neighboring vertices of $1$ are "visited", pop $1$ out of the stack. At this time, $S = [2]$.
  • Since all the neighboring vertices of $2$ are "visited", pop $2$ out of the stack and $S$ becomes empty again.

추가 예제