Minimum Crossing Cost in a Planar Tree

We are given a rooted tree with n nodes drawn on the plane under the following rules:

1. The root is node (1) and has depth (0).
2. For any node at depth (x), its vertical coordinate is (n-x+1) (in (\LaTeX): (n - x + 1)).
3. For every node, its children are arranged from left to right in increasing order of their labels.
4. Every edge of the tree is drawn as a straight line segment connecting a node and its parent.
5. Every leaf node has a ray starting at it, which is vertical (parallel to the (y)–axis) and extends indefinitely in the negative (y)–direction. The root has a ray extending indefinitely in the positive (y)–direction.
6. Any two segments or rays intersect only at the tree nodes.

Now, you are given (q) queries. In each query you are given two nodes (u) and (v). Starting at the point corresponding to node (u), you wish to move freely in the plane to reach the point corresponding to node (v). However, your path must not pass through any tree node except for the start and the destination. Moreover, every time your path crosses one of the drawn line segments or rays, you incur a cost of (1).

Your task is to determine, for each query, the minimum total cost (i.e. the minimum number of segment/ray crossings) required to travel from (u) to (v) under these restrictions.

Observation / Hint: Under the above drawing rules, one may prove that the minimum cost equals (|depth(u)-depth(v)|), where the depth of a node is defined as its distance (number of edges) from the root. In other words, if you pre‐compute the depth of every node (with (depth(1)=0)), then for every query the answer is (\lvert depth(u)-depth(v)\rvert).

inputFormat

The first line contains two integers (n) and (q) ((1 \leq n, q \leq 10^5)), representing the number of nodes in the tree and the number of queries respectively.

The second line contains (n-1) integers. For each (i) from (2) to (n), the (i)th integer is (p_i) ((1 \leq p_i < i)), denoting the parent of node (i). It is guaranteed that these values form a valid rooted tree with root (1).

Then (q) lines follow. Each of these lines contains two integers (u) and (v) ((1 \leq u, v \leq n)), representing a query.

outputFormat

For each query, output a single integer: the minimum cost (i.e. the minimum number of segment/ray crossings) to travel from node (u) to node (v).

sample

3 3
1 1
1 2
2 3
1 3

1
0
1