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