题目描述

Ht 镇由 $n$ 个 路口（编号从 $1$ 到 $n$）和 $m$ 条单行道连接而成。人们可以沿着道路从一个路口移动到另一个路口。从一个交叉路口到另一个交叉路口的路径长度，就是沿该路径要穿过的道路数量。从一个路口 $v$ 到另一个路口 $u$ 的最短路径，是起始于 $v$ 结束于 $u$ 且长度最小的路径。

小 W 住在 $s$ 路口附近，在 $t$ 路口附近的一幢大楼里工作。今天他选择了以下路径前往工作地点：$p_1,p_2,\cdots,p_k$，其中 $p_1 = s,p_k = t$，这个序列中的所有其他元素都是中间交叉点，按照小 W 到达这些交叉点的顺序排列。小 W 从未两次到达同一个交叉路口，因此这个序列中的所有元素都是两两不同的。请注意，你事先知道小 W 的路径（它是固定的），而且它不一定是从 $s$ 到 $t$ 的最短路径之一。

小 W 的车上安装了一套复杂的导航系统。让我们来描述一下它是如何工作的。当小 W 在路口 $s$ 开始他的旅程时，系统会选择从 $s$ 到 $t$ 的最短路径，并将其显示给小 W。如果小 W 选择沿着这条显示的最短路径从 $s$ 行驶到 $v$，那么导航仪就会向他显示同样的最短路径（显然，他一到达这个路口就会从 $v$ 开始）。但是，如果小 W 选择驶向另一个交叉路口 $w$，导航仪就会重建路径：小 W 一到达 $w$，导航系统就会选择从 $w$ 到 $t$ 的某个最短路径并显示给小 W。同样的过程一直持续到小 W 到达 $t$ 点。

小结一下：如果小 W 沿着系统推荐的道路前进，系统就会保留已经建立的最短路径；但如果小 W 选择了其他路径，系统就会按照同样的规则重建路径。

下面是一个例子。假设 Ht 镇的地图如下，小 W 沿着路径 $[ 1, 2, 3, 4 ]$ 行驶（$s=1, t=4$）：

• 当小 W 从 $1$ 出发时，系统会选择从 $1$ 到 $4$ 的最短路径，这样的路径只有一条，即 $[ 1, 5, 4 ]$；
• 小 W 选择开往 $2$，这条路径不在系统选择的路径上。当小W 到达 $2$ 时导航仪会重新选择一条从 $2$ 到 $4$ 的最短的路径， 例如 $[ 2, 6, 4 ]$（注意，它也可以选择 $[ 2, 3, 4 ]$）；
• 小 W 选择驶向 $3$，这与系统选择的路径不同。当小 W 到达 $3$ 时，导航仪重新选择了一条，即 $[ 3, 4 ]$；
• 小 W 到达 $4$，系统无需重建任何路径。

总的来说，在这种情况下，我们有 $2$ 次重建。请注意，如果系统选择的是 $[ 2, 3, 4 ]$ 而不是 $[ 2, 6, 4 ]$，则只有 $1$ 次重建。

这个例子告诉我们，即使 Ht 镇的地图和小 W 选择的路径保持不变，重建的次数也会不同。根据这些信息（地图和小 W 的路径），你会计算在旅程中可能发生的最少和最多的重建次数吗？

输入格式

第一行，两个整数 $n$ 和 $m$，分别表示 Ht 镇的交叉路口数和单行道数。

然后 $m$ 行，每行描述一条道路，包含两个整数 $u$ 和 $v$，表示从交叉点 $u$ 到 $v$ 有一条道路连接。Ht 镇的所有道路都是成对不同的，但如果有一条道路 $(u, v)$，道路 $(v, u)$ 也是可以出现的。

下面一行，一个整数 $k$，表示小 W 从家到工作地点的路径上的交叉路口数。

最后一行包含 $k$ 个互不相同的整数 $p1, p2, \cdots, pk$，表示按照小 W 到达的先后顺序经过的交叉路口。$p_1$ 是小 W 居住的交叉点（$p1 = s$），而 $p_k$ 是小 W 工作地点所在的交叉路口（$pk = t$)。可以保证，对于每个 $i ∈ [ 1, k - 1 ]$，从 $p_i$ 到 $p_{i+1}$ 的道路都是存在的，路径一定沿着 Ht 镇的道路走。

输出格式

两个整数：旅途中可能发生的最小和最大重建次数。

样例

6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4

1 2

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

0 0

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

0 3

数据范围

$20\%$ 的数据，$2\le n ≤ 20,2\le m ≤ 50$；

$100\%$ 的数据，$2 ≤ u,v,k,p_i\le n ≤ m ≤ 2\times10^5,u\neq v,p_1=s,p_k=t$，且对于 $\forall i,j\in[1,k](i\neq j)$ 满足 $p_i\neq p_j$。