← 返回题目列表

Codeforces · 1320/B

B. 导航系统

中文机器翻译题面 查看原题

Bertown 地图可以表示为一组 $$$n$$$ 交叉路口,编号从 $$$1$$$ 到 $$$n$$$,并由 $$$m$$$ 单向道路连接。可以沿着道路从任何十字路口移动到任何其他十字路口。从一个交叉路口到另一个交叉路口的某条路径的长度是人们必须沿着该路径穿过的道路的数量。从一个路口 $$$v$$$ 到另一个路口 $$$u$$$ 的最短路径是从 $$$v$$$ 开始,以 $$$u$$$ 结束的路径,并且是所有此类路径中长度最小的路径。

Polycarp 住在十字路口 $$$s$$$ 附近,并在十字路口 $$$t$$$ 附近的一栋大楼里工作。他每天开车从 $$$s$$$ 到 $$$t$$$。今天,他选择了以下通往工作场所的路径:$$$p_1$$$、$$$p_2$$$、...、$$$p_k$$$,其中 $$$p_1 = s$$$、$$$p_k = t$$$,以及该序列的所有其他元素都是中间交叉点,按照 Polycarp 到达它们的顺序列出。 Polycarp 从未两次到达同一个交叉点,因此该序列的所有元素都是成对不同的。请注意,您事先知道 Polycarp 的路径(它是固定的),并且它不一定是从 $$$s$$$ 到 $$$t$$$ 的最短路径之一。

波利卡普的汽车安装了复杂的导航系统。让我们描述一下它是如何工作的。当波利卡普在十字路口 $$$s$$$ 开始旅程时,系统会选择从 $$$s$$$ 到 $$$t$$$ 的最短路径并将其显示给波利卡普。我们将所选路径中的下一个交叉点表示为 $$$v$$$。如果Polycarp选择沿着从$$$s$$$到$$$v$$$的道路行驶,那么导航器会向他显示相同的最短路径(显然,一到达这个路口就从$$$v$$$开始)。然而,如果Polycarp选择开车到另一个路口$$$w$$$,导航器会重建路径:一旦Polycarp到达$$$w$$$,导航系统就会选择从$$$w$$$到$$$t$$$的最短路径并将其显示给Polycarp。同样的过程一直持续到Polycarp到达$$$t$$$:如果Polycarp沿着系统推荐的道路移动,它会保持已经建立的最短路径;但如果波利卡普选择其他路径,系统将按照相同的规则重建路径。

这是一个例子。假设 Bertown 的地图如下所示,Polycarp 沿着路径 $$$[1, 2, 3, 4]$$$ ($$$s = 1$$$, $$$t = 4$$$) 行驶:

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

1. 当Polycarp从$$$1$$$开始时,系统选择从$$$1$$$到$$$4$$$的最短路径。这样的路径只有一条,它是$$$[1, 5, 4]$$$;
2. Polycarp 选择行驶至 $$$2$$$,该路径不在系统选择的路径上。当Polycarp到达$$$2$$$时,导航器通过选择从$$$2$$$到$$$4$$$的最短路径来重建路径,例如$$$[2, 6, 4]$$$(注意它可以选择$$$[2, 3, 4]$$$);
3. Polycarp 选择行驶至 $$$3$$$,该路径不在系统选择的路径上。当Polycarp到达$$$3$$$时,导航器通过选择从$$$3$$$到$$$4$$$的唯一最短路径来重建路径,即$$$[3, 4]$$$;
4. Polycarp 沿着导航员选择的道路到达$$$4$$$,因此系统不需要重建任何东西。

总的来说,在这种情况下我们得到了 $$$2$$$ 重建。请注意,如果系统在第二步中选择 $$$[2, 3, 4]$$$ 而不是 $$$[2, 6, 4]$$$,则只会有 $$$1$$$ 重建(因为 Polycarp 沿着该路径走,所以系统在第三步中维护路径 $$$[3, 4]$$$)。

该示例向我们表明,即使 Bertown 地图和 Polycarp 选择的路径保持不变,重建次数也可能不同。有了这些信息(地图和坡旅甲的路径),你能确定旅途中可能发生的最小和最大重建次数吗?

输入

第一行包含两个整数 $$$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 中的所有道路都是成对不同的,这意味着每个有序对 $$$(u, v)$$$ 在这些 $$$m$$$ 行中最多出现一次(但如果存在一条道路 $$$(u, v)$$$,则该道路 $$$(v, u)$$$ 也可能出现)。

下面一行包含一个整数 $$$k$$$ ($$$2 \le k \le n$$$) — 坡旅甲从家到工作场所的路径中的交叉点数量。

最后一行包含 $$$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 的道路。

输出

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

示例

输入 #1

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

1 2

输入 #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

输出 #2

0 0

输入 #3

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

输出 #3

0 3