给定无向图 $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$ 个数一定按照从小到大的顺序给出。
输出一行一个数，表示可能的 DFS 序的数量。
8 7 5 1 2 1 3 1 6 3 4 2 5 7 8 8 7 1 2 3 7 8
4
$N ≤ 100，M ≤ 5000，K ≤ 18$
Comet OJ