Portals

The new company Sveriges Portaltrafik wants to change how Swedish commuters travel around the country. The company has proposed building a portal system in Sweden that uses fuel-efficient portals to replace trains, planes, and buses. The government has been asked to review the proposal in detail and has asked Swedish elite programmers for help. That is where you come in.

The portal system consists of $N$ portals placed at various locations in the country. Each portal $a$ has a destination portal $b$. This means that each time you enter $a$, you come out of $b$. Entering $b$ does not necessarily bring you back to $a$.

For a number of given start and end portals $a$ and $b$, the government wants to know how many times you need to enter the portal you emerge from to get from $a$ to $b$, or whether it is possible at all. For each query, answer with the number of times you need to enter portals to get from $a$ to $b$. If it is impossible, answer $-1$.

The first line contains the integer $N$, the number of portals. The next $N$ lines each contain an integer $1 \le d_i \le N$, meaning that portal $i$ leads to portal $d_i$. Portals are numbered from 1 to $N$, and they appear in the input in that order.

The next line contains the integer $Q$, the number of queries. The following $Q$ lines each contain two integers $1 \le s, e \le N$, giving a start portal $s$ and an end portal $e$. For every query, $s \neq e$.

Print $Q$ lines, one answer per query: the number of times you need to pass through portals to get from the start portal to the end portal. If it is impossible, print $-1$. Print each answer on its own line.

$1 \le N \le 50\,000$

$1 \le Q \le 70\,000$

The figure shows the network of the sample input. There are three queries. The first asks how many times you need to enter portals when you start at 1 and want to reach 2. Entering 1 takes you directly to 2, so the answer is 1. Getting from 1 to 4 takes three jumps. The answer to the last query is $-1$, because starting from 2 you can never reach 5, no matter how many times you pass through portals.