Problem F
Fjarflutningur

The recently founded Teleportation Institute of Iceland will revolutionize transportation in the country. The institute has put forth suggestions on how the energy-saving teleportation system could be constructed, thus making cars, busses and even airplanes obsolete. The government has now been tasked with taking a close look at this suggestion and they have even contacted the most skilled programmers of the country to help them. This is where you come in.

You have received an image of the plans to consider. The teleportation system consists of $N$ teleporters located around the country. Each teleporter $a$ has a particular teleporter $b$ as its destination. This means each time teleporter $a$ is entered, one exits in front of teleporter $b$. Note that entering teleporter $b$ does not necessarily bring you to the front of teleporter $a$. The idea put forth by the institute is that people start by entering one teleporter, then enter the teleporter they just exited, repeating until they are at their location.

The government now wants to know for different starting and ending teleporters $a$ and $b$ how many times you have to enter a teleporter to get from to $a$ to $b$ or whether it’s simply not possible. Please answer, for each query, how often you need to enter a teleporter to get from $a$ to $b$ or $-1$ if it’s not possible to get from $a$ to $b$ using the teleporters.

Help the government!

Input

The first line of the input contains an integer $N$ denoting the number of teleporters in the system. Then there are $N$ lines each containing an integer $1 \leq d_i \leq N$ that denote that if one enters teleporter $i$, one exits at teleporter $d_i$. The teleporters are numbered from $1$ to $N$ and appear in increasing order from $1$ to $N$ in the input.

Then there is a line with a single integer $Q$ denoting the number of queries that need to be answered. Then there are $Q$ lines each with two integers $1 \leq s, e \leq N$. These numbers denote the starting teleporter $s$ and the target teleporter $e$, your job is to answer how often one needs to enter a teleporter to get to teleporter $e$ if one starts at teleporter $s$. It will hold that $s \neq e$.

Output

Print $Q$ lines, one for each query: how often you need to enter a teleporter to get from the starting teleporter to the target one. If that’s not possible instead print $-1$. Each answer should be on its own line.

Explanation of Sample Inputs

Figure 1: Image of the first sample.

The teleporter system in the sample is shown above. We get three queries. In the first one we are asked how many teleporters one needs to enter if one starts at teleporter $1$ and need to get to teleporter $2$. Since one exits at teleporter $2$ when entering teleporter $1$, the answer is $1$. To go from teleporter $1$ to $4$ one needs to enter $3$ teleporters. For the last query the answer is $-1$, since no matter how often one enters a teleporter one never gets from $2$ to $5$.

Scoring

The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

5
2
3
4
3
4
3
1 2
1 4
2 5

1
3
-1