Hats and Flowers

You are given a rooted tree with n nodes numbered from 1 to n with root 1. Each node has a flower. When a hat starts at some node u to pick a flower, the flower at node v has an aroma defined as \(w_v = \operatorname{dis}(u,v)\), where \(\operatorname{dis}(u,v)\) is the unique distance (number of edges) between u and v in the tree. However, the hat can only pick one flower.

The hat has a time limit of t seconds. It starts at a given node and moves along the edges of the tree. The movement rules are as follows:

• When moving from a node to one of its children (i.e. moving away from the root), the hat uses 1 unit of time.
• When moving from a node to its parent (i.e. moving towards the root), the hat uses 0 units of time.

During the entire journey the remaining time must never drop below 0. For a journey that starts at node u, a valid route is one where the hat first may move freely (without time cost) towards an ancestor and then may move downward (costing time) from that ancestor. Formally, if the hat chooses an ancestor L of u and then goes from L to some node v by moving downward along the tree, the time cost is \(\max(0, d(v)-d(L))\) (where \(d(x)\) denotes the depth of node \(x\), with \(d(1)=0\)). The flower picked is at node v and its aroma is \(\operatorname{dis}(u, v)=d(u)+d(v)-2d(L)\).

You are given q independent queries. Each query is of the form: starting from node x_i with time t_i, what is the maximum possible aroma (i.e. maximum \(\operatorname{dis}(x_i, v)\)) of any flower that can be picked under the movement constraints?

Note: In some test cases the queries are given online, so you should process each query sequentially.

inputFormat

The input is given as follows:

1. The first line contains two integers n and q — the number of nodes in the tree and the number of queries.
2. The second line contains n-1 integers: p₂, p₃, ..., p_n, where p_i is the parent of node i (the tree is rooted at node 1).
3. Each of the next q lines contains two integers: x_i and t_i — the starting node for the hat and the time available, respectively.

outputFormat

For each query, output a single integer representing the maximum aroma (i.e. the maximum distance from x_i to some reachable node v under the movement constraints).

sample

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

2
2
3