{"raw_statement":[{"iden":"statement","content":"In the NN country, there are $n$ cities, numbered from $1$ to $n$, and $n - 1$ roads, connecting them. There is a roads path between any two cities.\n\nThere are $m$ bidirectional bus routes between cities. Buses drive between two cities taking the shortest path with stops in every city they drive through. Travelling by bus, you can travel from any stop on the route to any other. You can travel between cities only by bus.\n\nYou are interested in $q$ questions: is it possible to get from one city to another and what is the minimum number of buses you need to use for it?"},{"iden":"input","content":"The first line contains a single integer $n$ ($2 \\le n \\le 2 \\cdot 10^5$) — the number of cities.\n\nThe second line contains $n - 1$ integers $p_2, p_3, \\ldots, p_n$ ($1 \\le p_i &lt; i$), where $p_i$ means that cities $p_i$ and $i$ are connected by road.\n\nThe third line contains a single integer $m$ ($1 \\le m \\le 2 \\cdot 10^5$) — the number of bus routes.\n\nEach of the next $m$ lines contains $2$ integers $a$ and $b$ ($1 \\le a, b \\le n$, $a \\neq b$), meaning that there is a bus route between cities $a$ and $b$. It is possible that there is more than one route between two cities.\n\nThe next line contains a single integer $q$ ($1 \\le q \\le 2 \\cdot 10^5$) — the number of questions you are interested in.\n\nEach of the next $q$ lines contains $2$ integers $v$ and $u$ ($1 \\le v, u \\le n$, $v \\neq u$), meaning that you are interested if it is possible to get from city $v$ to city $u$ and what is the minimum number of buses you need to use for it."},{"iden":"output","content":"Print the answer for each question on a separate line. If there is no way to get from one city to another, print $-1$. Otherwise print the minimum number of buses you have to use."},{"iden":"examples","content":"Input\n\n7\n1 1 1 4 5 6\n4\n4 2\n5 4\n1 3\n6 7\n6\n4 5\n3 5\n7 2\n4 5\n3 2\n5 3\n\nOutput\n\n1\n3\n-1\n1\n2\n3\n\nInput\n\n7\n1 1 2 3 4 1\n4\n4 7\n3 5\n7 6\n7 6\n6\n4 6\n3 1\n3 2\n2 7\n6 3\n5 3\n\nOutput\n\n1\n-1\n-1\n1\n-1\n1"},{"iden":"note","content":"<center>![image](https://espresso.codeforces.com/16a4efe9afe96727316b2d4107867607c3fc6f99.png) Routes for first sample are marked on the picture.</center>"}],"translated_statement":[{"iden":"statement","content":"在 NN 国，有 $n$ 座城市，编号从 $1$ 到 $n$，以及 $n -1$ 条道路连接它们。任意两座城市之间都存在一条道路路径。\n\n有 $m$ 条双向公交线路连接城市。公交车沿最短路径在经过的每个城市停靠。乘坐公交车，你可以从路线上的任意一站前往另一站。你只能通过公交车在城市间旅行。\n\n你对 $q$ 个问题感兴趣：是否可以从一座城市到达另一座城市，以及为此需要使用的最少公交车数量是多少？\n\n第一行包含一个整数 $n$（$2 lt.eq n lt.eq 2 dot.op 10^5$）——城市数量。\n\n第二行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$（$1 lt.eq p_i < i$），其中 $p_i$ 表示城市 $p_i$ 和 $i$ 由一条道路连接。\n\n第三行包含一个整数 $m$（$1 lt.eq m lt.eq 2 dot.op 10^5$）——公交线路数量。\n\n接下来的 $m$ 行中，每行包含两个整数 $a$ 和 $b$（$1 lt.eq a, b lt.eq n$，$a eq.not b$），表示城市 $a$ 和 $b$ 之间有一条公交线路。两个城市之间可能存在多条线路。\n\n下一行包含一个整数 $q$（$1 lt.eq q lt.eq 2 dot.op 10^5$）——你感兴趣的查询数量。\n\n接下来的 $q$ 行中，每行包含两个整数 $v$ 和 $u$（$1 lt.eq v, u lt.eq n$，$v eq.not u$），表示你希望知道是否可以从城市 $v$ 到达城市 $u$，以及所需的最少公交车数量。\n\n请在每行输出一个查询的答案。如果无法从一座城市到达另一座城市，请输出 $-1$；否则输出所需的最少公交车数量。"},{"iden":"input","content":"第一行包含一个整数 $n$（$2 lt.eq n lt.eq 2 dot.op 10^5$）——城市数量。第二行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$（$1 lt.eq p_i < i$），其中 $p_i$ 表示城市 $p_i$ 和 $i$ 由一条道路连接。第三行包含一个整数 $m$（$1 lt.eq m lt.eq 2 dot.op 10^5$）——公交线路数量。接下来的 $m$ 行中，每行包含两个整数 $a$ 和 $b$（$1 lt.eq a, b lt.eq n$，$a eq.not b$），表示城市 $a$ 和 $b$ 之间有一条公交线路。两个城市之间可能存在多条线路。下一行包含一个整数 $q$（$1 lt.eq q lt.eq 2 dot.op 10^5$）——你感兴趣的查询数量。接下来的 $q$ 行中，每行包含两个整数 $v$ 和 $u$（$1 lt.eq v, u lt.eq n$，$v eq.not u$），表示你希望知道是否可以从城市 $v$ 到达城市 $u$，以及所需的最少公交车数量。"},{"iden":"output","content":"请在每行输出一个查询的答案。如果无法从一座城市到达另一座城市，请输出 $-1$；否则输出所需的最少公交车数量。"},{"iden":"examples","content":"输入71 1 1 4 5 644 25 41 36 764 53 57 24 53 25 3输出13-1123输入71 1 2 3 4 144 73 57 67 664 63 13 22 76 35 3输出1-1-11-11"},{"iden":"note","content":"第一个样例的线路在图中标出。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n $ vertices (cities) labeled $ 1 $ to $ n $, where $ V = \\{1, 2, \\dots, n\\} $, and $ E $ consists of $ n-1 $ undirected edges defined by parent relations: for each $ i \\in \\{2, \\dots, n\\} $, there is an edge between $ i $ and $ p_i $, with $ 1 \\le p_i < i $.  \n\nLet $ B = \\{ (a_j, b_j) \\mid j \\in \\{1, \\dots, m\\} \\} $ be a multiset of $ m $ bidirectional bus routes, where each route connects two distinct cities $ a_j, b_j \\in V $.  \n\nFor any bus route $ (a, b) $, define the *bus path* as the unique simple path between $ a $ and $ b $ in the tree $ T $. A passenger may board or alight at any city along this path.  \n\nLet $ G = (V, E_B) $ be the undirected graph where $ E_B $ contains an edge between two cities $ u, v \\in V $ if and only if there exists a bus route whose path in $ T $ includes both $ u $ and $ v $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 2 \\cdot 10^5 $  \n2. $ 1 \\le m \\le 2 \\cdot 10^5 $  \n3. $ 1 \\le q \\le 2 \\cdot 10^5 $  \n4. For each bus route $ (a, b) $: $ a, b \\in V $, $ a \\ne b $  \n5. For each query $ (v, u) $: $ v, u \\in V $, $ v \\ne u $  \n\n**Objective**  \nFor each query $ (v, u) $, compute the minimum number of bus routes required to travel from $ v $ to $ u $, where movement is allowed only via bus paths (i.e., you may traverse from any city on a bus route to any other city on the same route). If no such path exists, return $ -1 $.  \n\nFormally, define the graph $ H = (V, E_H) $, where $ \\{u, v\\} \\in E_H $ if there exists a bus route whose path in $ T $ contains both $ u $ and $ v $. Then, for each query $ (v, u) $, compute the shortest path distance (in terms of number of edges) from $ v $ to $ u $ in $ H $, or $ -1 $ if $ u $ is unreachable from $ v $.","simple_statement":null,"has_page_source":false}