序的计数 ### 题目描述 给定无向图 $G=\{V,E\}$，其中 $n=|V|,m=|E|$，$n$ 个点从 $1$ 到 $n$ 依次编号。 现在要求利用 DFS 即深度优先搜索。容易知道，利用 DFS 进行遍历的同时，我们可以将遍历到的点按照遍历的先后顺序记录下来，这样会得到一个点的序列，即一个 $1$ 到 $n$ 的排列。我们称这个排列为一个可能的 DFS 序。 显然不是所有 $1$ 到 $n$ 的排列都可能是 DFS 序的。现在这个 DFS 的过程进行到了一半，且恰好遍历了 $k$ 个不同的点 $\{u_1,u_2,...,u_k\}$，那么显然，这个进行到一半的 DFS 过程所对应的 DFS 序应该是这 $k$ 个数的一个排列。 现在请求出，当前这 $k$ 个遍历点能对应多少个不同的长度为 $k$ 的 DFS 序呢? ### 输入描述 输入文件第一行包含用空格隔开的三个整数，分别为 $n,m$ 和 $k$； 接下来 $m$ 行，每行包含两个用一个空格隔开的正整数 $u$ 和 $v$，表示图 $G$ 存在边 $(u,v)$。 最后一行包含 $k$ 个用空格隔开的正整数，描述当前已经遍历过的 $k$ 个点，其中第 $i$ 个数为 $u_i$。数据保证这 $k$ 个数一定按照从小到大的顺序给出。 其中，$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$。 ### 输出描述 输出一行一个数，表示可能的 DFS 序的数量。 ### 输入输出样例 #### 示例 1 >输入 ``` txt 8 7 5 1 2 1 3 1 6 3 4 2 5 7 8 8 7 1 2 3 7 8 ``` >输出 ``` txt 4 ```