Meeting at the Hippodrome

Limits: 4 sec., 512 MiB

This statement was translated automatically from Ukrainian.

On Zenik and Marichka’s farm, there is a hippodrome consisting of \(n\) plots, numbered from \(1\) to \(n\). The plots are connected by directed paths — exactly one path leaves each plot. The path from plot \(i\) leads to plot \(f_i\) (if \(f_i = i\), it means that the path starts and ends at the same plot \(i\)).

You need to answer \(q\) queries of the following type.

• There are two stallions: a bay and a black. The bay stallion is at plot \(u\), and the black stallion is at plot \(v\). In one minute, each horse can either stay in place or move along the path to the plot where it leads. Note that there is always one path from each plot. Calculate the minimum time in which both stallions can end up at the same plot of the hippodrome, or say that it is impossible.

Input

The first line gives two integers \(n\) and \(q\) — the number of plots in the hippodrome and the number of queries.

The second line gives \(n\) integers \(f_i\), describing the paths between the plots of the hippodrome.

The next \(q\) lines each give two integers \(u\) and \(v\) — the initial plots of the bay and black stallions.

Output

In \(q\) lines, output a single integer — the minimum time in minutes for both stallions to end up at the same plot, or -1 if this is impossible.

Constraints

\(1 \le n, q \le 3 \cdot 10^5\),

\(1 \le f_i, u, v \le n\).

Scoring consists of the following subtasks:

• 1 point for each sample example from the problem statement,

• 7 points: \(f_i = i\),

• 14 points: \(n, q \le 10^3\),

• 16 points: for each vertex \(v\) there exists a vertex \(u\) such that \(f_u = v\),

• 21 points: \(f_i \le i\),

• 26 points: from all vertices you can reach vertex 1,

• 14 points: without additional constraints.

You will get the points for a subtask only if your program passes all tests in that subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
8 5 2 3 1 2 4 7 6 7 1 5 6 7 6 8 2 5 4 7	2 1 1 2 -1

Input (stdin) сopy	Output (stdout) сopy
7 4 2 3 4 5 6 7 1 2 3 2 5 2 6 7 7	1 3 3 0

Notes

In the first example for the query \(u = 1, v = 5\), the answer is \(2\). That is, if the bay stallion starts at plot \(1\), and the black stallion at plot \(5\), they can meet at the same plot in two minutes.

• In the first minute, the bay stallion moves from plot \(1\) to plot \(2\), and the black stallion moves from plot \(5\) to plot \(4\).

• In the second minute, the black stallion moves from plot \(4\) to plot \(2\), and the bay stays in place at plot \(2\).

For the query \(u = 4, v = 7\), the bay and black stallions cannot end up at the same plot.