Background

Gensokyo, winter.

Once a year, the cedar cone trees growing on the high mountains bear fruit again.

Cirno somehow got $1,2,3\cdots9$ cedar cones, then happily ate $6$ of them, and in the end only $1$ cone was left.

Cirno felt sad because she would not be able to eat cedar cones in the future, so she decided to plant it by the beautiful Misty Lake.

On the first day, it sprouted.

On the second day, the cedar cone tree grew into a towering tree, covered with cedar cones.

Cirno had some questions she wanted to know before the cedar cones ripened, but now she was busy collecting cedar cones, so she threw the questions to you.

Problem Description

The cedar cone tree is a tree with $N$ nodes rooted at $1$.

In addition, Cirno has $Q$ queries. Each query is an ordered pair $(u,k)$, asking how many $k$-cousins node $u$ has.

We define:

The 1-father of node $u$ is the node on the path $(1, u)$ (excluding $u$) that is closest to $u$.

The $k$-father of node $u$ is the 1-father of the node “the $(k-1)$-father of $u$”.

The $k$-son of node $u$ is the set of all nodes whose $k$-father is $u$.

The $k$-cousin of node $u$ is the $k$-son of the node “the $k$-father of $u$” (excluding $u$ itself).

Input Format

The first line contains two integers $N$ and $Q$.

The second line contains $N-1$ integers. The $i$-th integer denotes the 1-father of node $i+1$.

The following $Q$ lines each contain an ordered pair $(u,k)$.

Output Format

Output one line with $Q$ numbers, where each number is the answer to a query. If $u$ does not have a $k$-father, output $0$.

5 2
1 2 1 4
2 1
3 2

1 1

Hint

Constraints: |Test Point ID|$N\le$|$Q\le$|Special Property| |----|----|----|-----| |1,2|$100$|$100$|| |3,4|$100$|$10^6$|| |5,6|$10^5$|$100$|| |7|$10^4$|$5000$|| |8,9,10|$10^5$|$10^5$|| |11,12,13,14|$10^6$|$10^6$|The tree is generated randomly| |15,16,17,18,19,20|$10^6$|$10^6$||

In addition, there is a set of hack testdata worth $20$ points.

Translated by ChatGPT 5