A8597 | Blood Cousins

Polycarpus got hold of a family relationship tree. The tree describes family relationships of $n$ people, numbered 1 through $n$ . Each person in the tree has no more than one parent.

Let's call person $a$ a 1-ancestor of person $b$ , if $a$ is the parent of $b$ .

Let's call person $a$ a $k$ -ancestor $(k>1)$ of person $b$ , if person $b$ has a 1-ancestor, and $a$ is a $(k-1)$ -ancestor of $b$ 's 1-ancestor.

Family relationships don't form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an $x$ -ancestor for himself, for some $x$ , $x>0$ ).

Let's call two people $x$ and $y$ $(x≠y)$ $p$ -th cousins $(p>0)$ , if there is person $z$ , who is a $p$ -ancestor of $x$ and a $p$ -ancestor of $y$ .

Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote $m$ pairs of integers $v_{i}$ , $p_{i}$ . Help him to calculate the number of $p_{i}$ -th cousins that person $v_{i}$ has, for each pair $v_{i}$ , $p_{i}$ .

The first input line contains a single integer $n$ $(1<=n<=10^{5})$ — the number of people in the tree. The next line contains $n$ space-separated integers $r_{1},r_{2},...,r_{n}$ , where $r_{i}$ $(1<=r_{i}<=n)$ is the number of person $i$ 's parent or 0, if person $i$ has no parent. It is guaranteed that family relationships don't form cycles.

The third line contains a single number $m$ $(1<=m<=10^{5})$ — the number of family relationship queries Polycarus has. Next $m$ lines contain pairs of space-separated integers. The $i$ -th line contains numbers $v_{i}$ , $p_{i}$ $(1<=v_{i},p_{i}<=n)$ .

Print $m$ space-separated integers — the answers to Polycarpus' queries. Print the answers to the queries in the order, in which the queries occur in the input.