← 返回题目列表

Codeforces · 983/E

E. NN国家

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

在NN国家,有$$$n$$$个城市,编号从$$$1$$$到$$$n$$$,以及连接它们的$$$n - 1$$$道路。任意两个城市之间都有一条公路。

城市之间有 $$$m$$$ 双向巴士路线。巴士在两个城市之间行驶,采用最短的路径,并在所经过的每个城市都有停靠点。乘坐巴士旅行,您可以从路线上的任何站点前往任何其他站点。您只能乘坐巴士在城市之间旅行。

您对 $$$q$$$ 问题感兴趣:是否可以从一个城市前往另一个城市以及您需要使用的最少公交车数量是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 城市数量。

第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i < i$$$),其中 $$$p_i$$$ 表示城市 $$$p_i$$$ 和 $$$i$$$ 有公路连接。

第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 公交路线的数量。

接下来的 $$$m$$$ 行包含 $$$2$$$ 整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$),这意味着城市 $$$a$$$ 和 $$$b$$$ 之间有一条巴士路线。两个城市之间可能有不止一条路线。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 您感兴趣的问题数。

接下来的 $$$q$$$ 行包含 $$$2$$$ 整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$),这意味着您有兴趣是否可以从城市 $$$v$$$ 到城市 $$$u$$$ 以及您需要的最少巴士数量是多少用于它。

输出

将每个问题的答案打印在单独的行上。如果无法从一个城市到达另一个城市,请打印 $$$-1$$$。否则打印您必须使用的最少巴士数量。

示例

输入 #1

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

输出 #1

1
3
-1
1
2
3

输入 #2

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

输出 #2

1
-1
-1
1
-1
1

注意

第一个样本的路线已标记在图片上。