Description

Given an undirected graph $G=\{V,E\}$, where $n=|V|$ and $m=|E|$. The $n$ vertices are numbered from $1$ to $n$.

Now we run DFS, i.e., depth-first search. It is easy to see that while performing DFS traversal, we can record the visited vertices in the order they are first visited. In this way we obtain a sequence of vertices, which is a permutation of $1$ to $n$. We call this permutation a possible DFS order.

Obviously, not every permutation of $1$ to $n$ can be a DFS order. Now suppose the DFS process is halfway done, and it has visited exactly $k$ distinct vertices $\{u_1,u_2,...,u_k\}$. Then clearly, the DFS order corresponding to this halfway DFS process should be a permutation of these $k$ numbers.

Now, please compute how many different DFS orders of length $k$ can correspond to the currently visited $k$ vertices.

Input Format

The first line contains three integers separated by spaces: $n$, $m$, and $k$.

The next $m$ lines each contain two positive integers $u$ and $v$ separated by one space, indicating that graph $G$ has an edge $(u,v)$.

The last line contains $k$ positive integers separated by spaces, describing the $k$ vertices that have already been visited. The $i$-th number is $u_i$. The testdata guarantees that these $k$ numbers are given in increasing order.

Output Format

Output one line with one number, which is the number of possible DFS orders.

8 7 5
1 2
1 3
1 6
3 4
2 5
7 8
8 7
1 2 3 7 8 

4

Hint

Constraints

• For $100\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 5 \times 10^3$, $1 \le k \le 18$, $1 \le u_i \le n$, $1 \leq u, v \leq n$.

Translated by ChatGPT 5