Joining Couples#6604

Joining Couples

2 secondi

64 megabyte

Molto difficile

Air traffic regulations in Nlogonia require that each city must register exactly one outbound flight to another city. Passengers can use this flight only in the direction registered, that is, there may be a flight registered from city $X$ to city $Y$ and no flight registered from city $Y$ to city $X$ . Thus, the number of registered flights is equal to the number of cities. This rule, as one can imagine, makes air travel somewhat complicated, but tradition and a strong ruling by the Queen makes any changes difficult. Besides, some companies even make a profit from the problems caused by the rule.

The Association for Couple Matching (ACM) is setting up a new service to help customers find their long lasting soulmates: the Internet Connecting Program for Couples (ICPC). The service consists of computing the minimum total number of flights a couple needs to take to meet one another (perhaps in a city where neither of them lives in). Assuming the couple's starting cities are $A$ and $B$ , the agency will try to find a city $C$ such that $C$ is reachable by air travel from both $A$ and $B$ , and 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$ is minimized. Note that $C$ may be equal to $A$ or $B$ or both.

You will be given the list of all available flights, and a list of queries consisting of pairs of cities where the members of a couple live. For each query, you must compute the minimum total number of flights that are needed for them to meet.

Input

Each test case is described using several lines. The first line contains an integer $N$ representing the number of cities ( $2 \leq N \leq 1 0^{5}$ 2 \le N \le 10^5). Cities are identified by different integers from $1$ to $N$ . The second line contains $N$ integers $F_{i}$ F_i, where $F_{i}$ F_i indicates that the registered outbound flight from city $i$ is to city $F_{i}$ F_i ( $1 \leq F_{i} \leq N$ 1 \le F_i \le N, $F_{i} \neq = i$ F_i \ne i for $i = 1, 2, \dots, N$ i = 1, 2, \ldots, N). The third line contains an integer $Q$ representing the number of queries ( $1 \leq Q \leq 1 0^{5}$ 1 \le Q \le 10^5). Each of the next $Q$ lines describes a query with two integers $A$ and $B$ indicating the couple's starting cities ( $1 \leq A, B \leq N$ 1 \le A, B \le N). Within each test case, if it is possible to travel by air from city $X$ to city $Y$ , the maximum number of flights needed to do so is $1 0^{4}$ 10^4.

Output

For each test case output $Q$ lines. In the $i$ -th line write an integer with the answer to the $i$ -th query. If the corresponding couple can meet by air travel, write the minimum total number of flights that the couple must take to meet one another; if it is impossible for the couple to meet by air travel, write the number ' $- 1$ '.

Esempi

Esempio 1