Snow Pine Tree Cousins

Given a tree with N nodes rooted at node 1 (the Snow Pine Tree), and Q queries, each query is a tuple \((u,k)\) asking for the number of \(k\)-cousins of node \(u\).

Definitions:

• The \(1\)-father of a node \(u\) is defined as the node in the path from \(1\) to \(u\) (excluding \(u\)) that is closest to \(u\).
• The \(k\)-father of node \(u\) is the \(1\)-father of the \((k-1)\)-father of \(u\).
• The \(k\)-son of node \(u\) is any node whose \(k\)-father is \(u\).
• The \(k\)-cousins of node \(u\) are defined as the set of nodes that are \(k\)-sons of \(u\)'s \(k\)-father, excluding \(u\) itself.

You are to answer each query by determining the number of \(k\)-cousins for the given node \(u\). In other words, if \(f\) is the \(k\)-father of \(u\), then the answer is the number of nodes \(v\) (other than \(u\)) such that the \(k\)-father of \(v\) is \(f\).

inputFormat

The first line contains two integers \(N\) and \(Q\): the number of nodes and the number of queries.

The second line contains \(N-1\) integers. The \(i\)-th integer denotes the parent of node \(i+1\) (for \(i = 1, 2, \dots, N-1\)).

Each of the following \(Q\) lines contains two integers \(u\) and \(k\), representing a query.

outputFormat

For each query, output the number of \(k\)-cousins of node \(u\) on a separate line.

sample

7 3
1 1 2 2 3 3
4 1
6 2
2 1

1
3
1