CF1320B.Navigation System

The map of Bertown can be represented as a set of $n$ intersections, numbered from $1$ to $n$ and connected by $m$ one-way roads. It is possible to move along the roads from any intersection to any other intersection. The length of some path from one intersection to another is the number of roads that one has to traverse along the path. The shortest path from one intersection $v$ to another intersection $u$ is the path that starts in $v$, ends in $u$ and has the minimum length among all such paths.

Polycarp lives near the intersection $s$ and works in a building near the intersection $t$. Every day he gets from $s$ to $t$ by car. Today he has chosen the following path to his workplace: $p_1$, $p_2$, ..., $p_k$, where $p_1 = s$, $p_k = t$, and all other elements of this sequence are the intermediate intersections, listed in the order Polycarp arrived at them. Polycarp never arrived at the same intersection twice, so all elements of this sequence are pairwise distinct. Note that you know Polycarp's path beforehand (it is fixed), and it is not necessarily one of the shortest paths from $s$ to $t$.

Polycarp's car has a complex navigation system installed in it. Let's describe how it works. When Polycarp starts his journey at the intersection $s$, the system chooses some shortest path from $s$ to $t$ and shows it to Polycarp. Let's denote the next intersection in the chosen path as $v$. If Polycarp chooses to drive along the road from $s$ to $v$, then the navigator shows him the same shortest path (obviously, starting from $v$ as soon as he arrives at this intersection). However, if Polycarp chooses to drive to another intersection $w$ instead, the navigator rebuilds the path: as soon as Polycarp arrives at $w$, the navigation system chooses some shortest path from $w$ to $t$ and shows it to Polycarp. The same process continues until Polycarp arrives at $t$: if Polycarp moves along the road recommended by the system, it maintains the shortest path it has already built; but if Polycarp chooses some other path, the system rebuilds the path by the same rules.

Here is an example. Suppose the map of Bertown looks as follows, and Polycarp drives along the path $[1, 2, 3, 4]$ ($s = 1$, $t = 4$):

Check the picture by the link http://tk.codeforces.com/a.png

1. When Polycarp starts at $1$, the system chooses some shortest path from $1$ to $4$. There is only one such path, it is $[1, 5, 4]$;
2. Polycarp chooses to drive to $2$, which is not along the path chosen by the system. When Polycarp arrives at $2$, the navigator rebuilds the path by choosing some shortest path from $2$ to $4$, for example, $[2, 6, 4]$ (note that it could choose $[2, 3, 4]$);
3. Polycarp chooses to drive to $3$, which is not along the path chosen by the system. When Polycarp arrives at $3$, the navigator rebuilds the path by choosing the only shortest path from $3$ to $4$, which is $[3, 4]$;
4. Polycarp arrives at $4$ along the road chosen by the navigator, so the system does not have to rebuild anything.

Overall, we get $2$ rebuilds in this scenario. Note that if the system chose $[2, 3, 4]$ instead of $[2, 6, 4]$ during the second step, there would be only $1$ rebuild (since Polycarp goes along the path, so the system maintains the path $[3, 4]$ during the third step).

The example shows us that the number of rebuilds can differ even if the map of Bertown and the path chosen by Polycarp stays the same. Given this information (the map and Polycarp's path), can you determine the minimum and the maximum number of rebuilds that could have happened during the journey?

伯顿市的地图可以表示为一个包含 $n$ 个路口（编号从 $1$ 到 $n$）的集合，这些路口由 $m$ 条单向道路连接。任意两个路口之间均存在一条路径（即图是强连通的）。一条从某个路口到另一路口的路径的长度定义为该路径所经过的道路数量。从路口 $v$ 到路口 $u$ 的最短路径是指所有从 $v$ 出发、在 $u$ 结束的路径中长度最小的一条。

波利卡普住在靠近路口 $s$ 的地方，工作地点则靠近路口 $t$。他每天开车从 $s$ 前往 $t$。今天，他选择了一条前往工作地点的固定路径：$p_1, p_2, \dots, p_k$，其中 $p_1 = s$，$p_k = t$，其余元素为途中依次经过的中间路口。波利卡普从未重复经过同一路口，因此该序列中所有元素两两互异。注意：你已预先知道波利卡普的完整路径（它是固定的），但该路径不一定是 $s$ 到 $t$ 的某条最短路径。

波利卡普的汽车装有一套复杂的导航系统。其工作方式如下：当波利卡普从路口 $s$ 出发时，系统会选定某条从 $s$ 到 $t$ 的最短路径，并向波利卡普显示。记该选定路径中 $s$ 之后的下一个路口为 $v$。若波利卡普选择沿 $s \to v$ 这条道路行驶，则导航系统继续显示同一条最短路径（显然，当他抵达 $v$ 后，路径将从 $v$ 开始继续显示）。然而，若波利卡普选择驶向另一个路口 $w$（即 $w \ne v$），则导航系统将重新规划路径：一旦波利卡普抵达 $w$，系统立即重新选定某条从 $w$ 到 $t$ 的最短路径并显示给波利卡普。此过程持续进行，直至波利卡普抵达 $t$：若他始终按系统推荐的道路行驶，则系统维持当前已构建的最短路径；若他选择了其他道路，则系统按上述规则重新规划路径。

下面是一个示例。假设伯顿市地图如下图所示，且波利卡普的行驶路径为 $[1, 2, 3, 4]$（即 $s = 1$，$t = 4$）：

查看图片链接：http://tk.codeforces.com/a.png

1. 波利卡普从 $1$ 出发时，系统选定某条从 $1$ 到 $4$ 的最短路径。此处仅存在唯一一条最短路径：$[1, 5, 4]$；
2. 波利卡普选择驶向 $2$，而该选择并未遵循系统推荐的路径。当他抵达 $2$ 时，导航系统重新规划路径，选定某条从 $2$ 到 $4$ 的最短路径，例如 $[2, 6, 4]$（注意：它也有可能选定 $[2, 3, 4]$）；
3. 波利卡普选择驶向 $3$，该选择同样未遵循系统当前推荐的路径。当他抵达 $3$ 时，导航系统再次重新规划路径，选定从 $3$ 到 $4$ 的唯一最短路径：$[3, 4]$；
4. 波利卡普随后沿导航系统推荐的道路（即 $3 \to 4$）抵达 $4$，因此系统无需再次重建路径。

综上，本场景中共发生了 $2$ 次重建。注意：若系统在第二步中选定的是 $[2, 3, 4]$ 而非 $[2, 6, 4]$，则整个过程中仅发生 $1$ 次重建（因为波利卡普第三步恰好沿系统推荐路径 $3 \to 4$ 行驶，系统可维持该路径而无需重建）。

该示例表明：即使伯顿市地图和波利卡普所选路径完全相同，重建次数仍可能不同。现给定地图信息（即图结构）及波利卡普的路径，你能否确定本次行程中可能发生的最小重建次数与最大重建次数？

The first line contains two integers $n$ and $m$ ($2 \le n \le m \le 2 \cdot 10^5$) — the number of intersections and one-way roads in Bertown, respectively.

Then $m$ lines follow, each describing a road. Each line contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) denoting a road from intersection $u$ to intersection $v$. All roads in Bertown are pairwise distinct, which means that each ordered pair $(u, v)$ appears at most once in these $m$ lines (but if there is a road $(u, v)$, the road $(v, u)$ can also appear).

The following line contains one integer $k$ ($2 \le k \le n$) — the number of intersections in Polycarp's path from home to his workplace.

The last line contains $k$ integers $p_1$, $p_2$, ..., $p_k$ ($1 \le p_i \le n$, all these integers are pairwise distinct) — the intersections along Polycarp's path in the order he arrived at them. $p_1$ is the intersection where Polycarp lives ($s = p_1$), and $p_k$ is the intersection where Polycarp's workplace is situated ($t = p_k$). It is guaranteed that for every $i \in [1, k - 1]$ the road from $p_i$ to $p_{i + 1}$ exists, so the path goes along the roads of Bertown.

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le m \le 2 \cdot 10^5$），分别表示 Bertown 中的交叉路口数量和单向道路数量。

接下来是 $m$ 行，每行描述一条道路。每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，且 $u \ne v$），表示一条从交叉路口 $u$ 指向交叉路口 $v$ 的道路。Bertown 中的所有道路两两不同，即在上述 $m$ 行中，每个有序对 $(u, v)$ 至多出现一次（但若存在道路 $(u, v)$，则道路 $(v, u)$ 也可能同时存在）。

随后一行包含一个整数 $k$（$2 \le k \le n$），表示 Polycarp 从家到工作地点所经过的交叉路口数量。

最后一行包含 $k$ 个整数 $p_1$, $p_2$, ..., $p_k$（$1 \le p_i \le n$，且这些整数两两不同），表示 Polycarp 路径上依次经过的交叉路口。其中 $p_1$ 是 Polycarp 的住所所在交叉路口（即起点 $s = p_1$），而 $p_k$ 是 Polycarp 工作地点所在交叉路口（即终点 $t = p_k$）。题目保证：对每个 $i \in [1, k - 1]$，均存在从 $p_i$ 到 $p_{i + 1}$ 的道路，因此该路径完全沿 Bertown 的道路行进。

Print two integers: the minimum and the maximum number of rebuilds that could have happened during the journey.

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