Joining Couples

Time limit1sMemory limit128 MB

Summary

Each city has one directed outbound flight, forming a functional graph; for each query find the minimum combined distance from two starting cities to any common reachable city, or -1.

Level: Hard8 of 10
Topics: Graph, Tree, Binary search, Prefix sum
Solved: No attempts yet

Problem

Nlogonia's air-traffic rules require every city to register exactly one outbound flight to another city. A flight may be used only in its registered direction: a registered flight from city $X$ to city $Y$ does not imply a flight from $Y$ to $X$ . Because every city registers exactly one outbound flight, the total number of registered flights equals the number of cities.

The Association for Couple Matching runs a service that computes the minimum total number of flights a couple must take in order to meet, possibly in a city where neither of them lives. If the two people start in cities $A$ and $B$ , the service looks for a city $C$ that is reachable by air from both $A$ and $B$ and minimizes the sum of the number of flights needed to go from $A$ to $C$ and the number of flights needed to go from $B$ to $C$ . City $C$ may be equal to $A$ , to $B$ , or to both.

You are given the list of all registered flights together with several queries, each giving the two cities where the members of a couple live. For each query, compute the minimum total number of flights the couple needs in order to meet.

Input

The input contains several test cases and ends at end of file.

Each test case is described on several lines:

The first line contains an integer $N$ , the number of cities ( $2 \le N \le 10^5$ ). Cities are numbered from $1$ to $N$ .
The second line contains $N$ integers $F_1, F_2, \ldots, F_N$ , where $F_i$ is the city that the single outbound flight registered from city $i$ goes to ( $1 \le F_i \le N$ and $F_i \ne i$ ).
The third line contains an integer $Q$ , the number of queries ( $1 \le Q \le 10^5$ ).
Each of the next $Q$ lines contains two integers $A$ and $B$ , the cities where the members of one couple live ( $1 \le A, B \le N$ ).

Within a single test case, whenever it is possible to travel by air from a city $X$ to a city $Y$ , the number of flights needed to do so is at most $10^4$ .

Output

For each query, output one line. If the couple can meet by air travel, print the minimum total number of flights they must take to meet; if they can never meet, print $-1$ . Print the answers for all test cases, in order.

Examples4

Example 1

Input

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

Expected output

Example 2
Input
```
2
2 1
4
1 1
1 2
2 1
2 2
```
Expected output
```
0
1
1
0
```
Example 3
Input
```
4
2 1 4 3
4
1 3
1 2
3 4
2 4
```
Expected output
```
-1
1
1
-1
```

Example 4

Input

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

Expected output