题目描述

给定无向图 $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

提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $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$。