P6238 [JSOI2011] Counting DFS Orders.

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.

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 one line with one number, which is the number of possible DFS orders.

#### 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