NN country
Contest: Codeforces Round 483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]
Difficulty rating: 2800
Tags: binary search, data structures, trees

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.

There 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.

You 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?

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of cities.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i < i$$$), where $$$p_i$$$ means that cities $$$p_i$$$ and $$$i$$$ are connected by road.

The third line contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of bus routes.

Each 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.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of questions you are interested in.

Each 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.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Routes for first sample are marked on the picture.

Example input:
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

Example output:
1
3
-1
1
2
3

Example input:
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

Example output:
1
-1
-1
1
-1
1

Editorial:
Let's say we go down when we go towards the root, and we go up when we go against the root. Also we say that vertex $$$a$$$ lower than vertex $$$b$$$ if $$$a$$$ is closer to the root.
Each way from $$$v$$$ to $$$u$$$ can be represented as two parts: at first we go down from $$$v$$$ to $$$lca$$$ and then we go up from $$$lca$$$ to $$$u$$$.
Let's say we have to use $$$a$$$ buses to go from $$$v$$$ to $$$lca$$$ and $$$b$$$ buses to go from $$$lca$$$ to $$$u$$$. Let's learn how to calculate $$$a$$$ and $$$b$$$ fast. Firstly, notice that we can move down greedily. So we calculate $$$lowest[v]$$$ as the lowest vertex, where we can go from $$$v$$$ using only one bus. Secondly, notice that we can now build binary lifting on $$$lowest$$$.
The answer is either $$$a + b$$$ or $$$a + b - 1$$$. Let's say the lowest vertex we can go from $$$v$$$ using $$$a - 1$$$ buses is $$$l_v$$$ and for $$$u$$$ and $$$b - 1$$$ buses it's $$$l_u$$$. $$$l_v$$$ and $$$l_u$$$ can be also calculated using binary lifting on $$$lowest$$$. Then, if there is a route connecting $$$l_v$$$ and $$$l_u$$$, the answer is $$$a + b - 1$$$ and it's $$$a + b$$$ otherwise.
Let's calculate $$$l_v$$$ and $$$l_u$$$ for all the queries.
Now we build an euler's tour. For each we now know the interval, corresponding to it's subtree. Let's say it is $$$[time\_in[v], time\_out[v])$$$. Then we run dfs again and do the following: when we came into $$$l_v$$$ we ask for sum on $$$[time\_in[l_u], time\_out[l_u])$$$. Now for each way, starting in $$$l_v$$$ we add $$$1$$$ to its other end. Now we run dfs for all of its children. And now we ask for sum on $$$[time\_in[l_u], time\_out[l_u])$$$ for the second time. If it changed the route connecting $$$l_v$$$ and $$$l_u$$$ exists.
Asymptotics is $$$O(n \cdot log(n) + m \cdot log(n) + q \cdot log(n))$$$.
Read the solution for better understanding. It tried to make it as readable as possible.
Solution